[其他] 對稱加密的破解複雜度

看板Math作者 (QQ)時間2年前 (2022/05/01 17:35), 2年前編輯推噓5(5推 0噓 46→)
留言51則, 4人參與, 2年前最新討論串1/1
最近為了產品應用在實作一些小型的加密 發現有個怪怪的地方 我先把要討論的對稱加密寫成數學語言: ------------------------------------- S_n:={0,1}^n f_k:S_n→S_n 是可逆函數, for each k€S_m (m可能等於n, 無所謂, key長度而已) ------------------------------------- 對稱性加密的原理就是f_k的演算法是公開的, 但是k是自己/信賴的人保留的 也就是說, 今天自己選擇一個k, 把明文 x€{0,1}^n 轉到暗文 y=f_k(x)€S_n後 沒有k的人拿到y也沒用, 因為隨便一個k'都能還原出x', 但是可能不是x 只有正確的k才會保證還原正確的x 而如果要暴力破解, 就要嘗試2^m個key, 這對於m=256來說就是天文數字 但是不暴力破解的話, 會不會因為f_k太簡單而導致不用嘗試到2^m個key就破解了 原本我猜測是肯定的, 就是f_k要複雜, 如AES加密算法, 可能現今對他還沒想到除了 暴力破解外的解法 但是突然出現一個矛盾...我今天設計一個非常簡單的f_k, 就單純是xor(互斥邏輯運算) 舉例來說, m=n=2, k=(0,0), x=(1,0),則f_k(x) = (1,0) 然後拿這個f_k機制來進行對稱性加密, k自己保留 我目前發現對方除了暴力破解外也無他法 即便他知道我用的是最簡單的xor, 但是沒拿到真正的k, 他解出來的明文不一定是對的 但是如果xor就可以了, 也不必存在AES這些運算量高的算法 至此我再用原始函數條件去想, 確實可能存在不同的k', 但是可以得到真正的明文x 也就是說, 如果我私有k滿足f_k(x) = y, 其實存在其他k'滿足f_k'(x) = y 這是否就是AES之類對稱加密防護的機制? 也就是說, 一個robus的對稱性加密需要額外滿足: 對所有x€S_n, F(k) := f_k(x), F要是一對一 也就是說, 如果f_k(x) = f_k'(x), 則k=k' (大致上看起來m>=n才有機會讓綠色成立) ---------------------------------------------------------------------- 總之想請問的是, 對稱性加密關鍵是否就真的在於綠色以至於只剩暴力破解來保障安全性 謝謝幫忙~~ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 59.102.225.191 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1651397705.A.5AD.html
→
05/01 20:41, 2年前 , 1F
你xor的例子就是one-time-pad k得和明文一樣長
05/01 20:41, 1F
→
05/01 20:41, 2年前 , 2F
而且只能用一次
05/01 20:41, 2F
→
05/01 20:44, 2年前 , 3F
AES的key是固定大小 而且可以用很多次 甚至可以讓攻
05/01 20:44, 3F
→
05/01 20:46, 2年前 , 4F
擊者拿到f_k,f_k^-1 然後還是不知道k是什麼
05/01 20:46, 4F
→
05/01 20:50, 2年前 , 5F
可以看一下Pseudorandom Functions
05/01 20:50, 5F
int大你意思是AES的f_k可以完全給別人運作(比如某個包好的程式檔) 但是使用的人無法知道裡面的k是什麼? 這確實是xor做不到的事情, 如果拿的到xor的f_k, 他只要輸入一個input就知道是k是什麼了 不過我剛剛發現xor會滿足綠色的式子耶... 今天看你敘述xor的缺點, 好像是針對"方便性"以及"泛用性" 但是單純論安全性的話, 是不是很安全? 因為只能暴力破解 證明如下: 我選了一個k€S_n, 用xor加密了明文x€S_n, 得到y = x xor k, y€S_n 駭客偷看到y, 想要得到x的話就必須去窮舉所有的k'€S_n 假設存在另外一個k'使得y = x xor k' 那由xor的性質可以得到k=k', 也就是說他必須選到我當初選的k 我有少考慮到什麼嗎?
推
05/01 22:20, 2年前 , 6F
google: information theoretic security
05/01 22:20, 6F
看wiki好像在敘述一些"因為訊息不足, 即便時間無限也永遠無法被破解"的加密算法 但是我從接觸加密相關的資料以來, 每一種方法如果目前仍在用, 都是可以暴力破解的 只是時間如果長到誇張就歸納為現在無法破解 想額外問一下, 有對於"可/不可破解"的數學定義或是實務定義嗎? 數學定義之前是看過一些用"機率加運算時間"的定義方式 而實務定義的話, 是否只能說"到目前為止只能用暴力破解"來當不可破解的定義? 只是不排除未來某一天有人剛好想到很快的演算法, 或是猜到key, 或是簡化出數學式 舉例來說, Σ_{k=1~N} (-1)^k 的答案是多少, 當N=2^1000時 我聲稱這個在數十年電腦都跑不完(無法暴力破解) 但是任何一個小學生都能告訴這個答案是多少(簡化數學式了) 我這個例子是想表達是否實務上的加密方式都有這個危險, 只是目前沒發生而已? (然後information theoretic security就是說這件事絕對不能發生, 即無解) ※ 編輯: znmkhxrw (59.102.225.191 臺灣), 05/02/2022 02:13:22
推
05/02 07:21, 2年前 , 7F
你舉的XOR加密的例子基本上有n個獨立sample的話用高
05/02 07:21, 7F
→
05/02 07:21, 2年前 , 8F
斯消去就有高機率可以反推k了
05/02 07:21, 8F
c大你應該是指如果對方有f_k的程式, 那這樣當然別人隨便一個input輸入後就知道k是什 麼了 可是我的意思是對方只知道我的y, 而y是我自己由某個f_k產生的, 即便讓他知道f_k的設 計只是跟某個k做xor, 他也猜不到這個k是什麼
推
05/02 07:24, 2年前 , 9F
Information theoretic secure的要求會imply就算你
05/02 07:24, 9F
→
05/02 07:24, 2年前 , 10F
有一堆sample也沒辦法反推密鑰
05/02 07:24, 10F
推
05/02 07:27, 2年前 , 11F
然後加密安全性也不是只有information theoretic se
05/02 07:27, 11F
→
05/02 07:27, 2年前 , 12F
cure這個定義 密碼學研究據我所知更常用的是類似pol
05/02 07:27, 12F
→
05/02 07:27, 2年前 , 13F
ynomial time indistinguishable之類的標準
05/02 07:27, 13F
這應該就是我看到的用機率測度加上時間複雜度所下的定義了
推
05/02 07:51, 2年前 , 14F
說起來你有去查「one time pad」這個名詞了嗎?
05/02 07:51, 14F
→
05/02 07:52, 2年前 , 15F
你最一開始提的 XOR 做法就是這個
05/02 07:52, 15F
→
05/02 07:52, 2年前 , 16F
而且確實有人證明了 (那位大名鼎鼎的 Shannon) 說
05/02 07:52, 16F
→
05/02 07:52, 2年前 , 17F
只要 one time pad 的鑰匙至少跟訊息一樣長
05/02 07:52, 17F
→
05/02 07:53, 2年前 , 18F
且每次都重新產生不重覆使用, 那它是最安全的密碼
05/02 07:53, 18F
→
05/02 07:54, 2年前 , 19F
但是實務加密上我們還有鑰匙分送問題及應用效率問題
05/02 07:54, 19F
→
05/02 07:54, 2年前 , 20F
你要傳一個訊息還要傳一個跟這訊息一樣長的密碼
05/02 07:54, 20F
→
05/02 07:55, 2年前 , 21F
這就算不上是個「安全」的密碼應用了
05/02 07:55, 21F
→
05/02 07:56, 2年前 , 22F
現代的密碼應用確實都是在找一些目前認為計算上很難
05/02 07:56, 22F
→
05/02 07:56, 2年前 , 23F
的問題放入演算法的核心; 這裡會應用到你應該聽過的
05/02 07:56, 23F
→
05/02 07:57, 2年前 , 24F
P vs NP 問題, 關於這個可以看我這篇 #1GPBcQPe
05/02 07:57, 24F
→
05/02 08:00, 2年前 , 25F
這也能算是對你的「可/不可破解的數學定義」的回答
05/02 08:00, 25F
→
05/02 08:01, 2年前 , 26F
目前認為的「很難破解」基本上就是「要破解它要解
05/02 08:01, 26F
→
05/02 08:02, 2年前 , 27F
一個 NP 完全問題, 但現在一般認為這不能很快做到」
05/02 08:02, 27F
嗨L大, 讀了#1GPBcQPe這篇受益良多, 裡面確實還有一個變因是"計算模型"
→
05/02 08:07, 2年前 , 28F
噢, 回頭看到你在談的是對稱加密...
05/02 08:07, 28F
→
05/02 08:07, 2年前 , 29F
這方面的話, 有一個關鍵字是「Feistel Cipher」
05/02 08:07, 29F
→
05/02 08:07, 2年前 , 30F
現在大多數的對稱加密的架構都是這個東西
05/02 08:07, 30F
→
05/02 08:08, 2年前 , 31F
這是因為它也有理論證明只要當中的單輪計算符合
05/02 08:08, 31F
→
05/02 08:08, 2年前 , 32F
某些條件的話, 那全部計算結果就具有某個計算強度在
05/02 08:08, 32F
→
05/02 08:09, 2年前 , 33F
你的問題可以去研究這東西跟它的安全性證明
05/02 08:09, 33F
→
05/02 08:10, 2年前 , 34F
各種不同的對稱加密就是單輪計算的設計不一樣而已
05/02 08:10, 34F
→
05/02 08:11, 2年前 , 35F
因此對於這些對稱加密的演算法的破解也就會專注在
05/02 08:11, 35F
→
05/02 08:11, 2年前 , 36F
破解所設計的單輪運算, 看能不能強迫造成什麼性質
05/02 08:11, 36F
→
05/02 08:11, 2年前 , 37F
使其得以推算出中間結果甚至密鑰
05/02 08:11, 37F
這些關鍵字以我現有的密碼學知識來說有點難串起來... 有點像是讀了reference 1 & 2後, 覺得他們好像有點關係, 又好像是在講不同的東西 我用對稱性加密敘述一下我發問的動機: 1. 想設計簡單的f_k, 對於每個k€S_n都存在在S_n的可逆函數f_k 2. 直覺的拿xor跟permutation這兩個去做組合, 但是馬上發現幾件事: (1) 肉眼看起來複雜的加密結果, 對電腦而言卻不一定 (2) 肉眼看起來複雜的加密程式, 對破解而言卻不一定 以xor跟permutation所做的f_k為例, 因為證明了: (a) 多個xor可以合併成一個xor (b) 多個permutation可以合併成一個permutation (c) xor跟permutation可交換, 只是差別在xor的值做個改變罷了 所以得出了如果f_k的設計是數以千計的xor跟permutation所組成 那對破解者來說僅是一次的xor跟permutation所組成 這個問題也讓我特別留意所設計的算法有沒有白做事 這也是為什麼我舉了Σ_{k=1~N} (-1)^k當例子, 實際算運算量很高 但是根本不用算就可以得到答案, 只要你找到快速的破解法 3. 承2.-(2), 我無法窮舉所有的破解方式, 說不定只是我以為只能暴力解 但是有其他破解者能找到很快的破解法 這也是為什麼我猜測RSA, AES...之類的加密算法是迄今沒有速解 但是不能保證未來沒有 也就是因為1.~3., 讓我去好奇跟搜尋加密破解性的定義 然後就得到一些統計測度論以及時間複雜度數學上的定義... 之後越查越覺得複雜, 因為我起初的問題聽起來很簡單: 破解難易度 還是就是因為很難一致定義破解難易度, 才有以不同切入點所得到的定義? (有些用時間複雜度, 有些用資訊商...any other) ---------------------------------------------------- 以上就是我的發問動機以及思考細項, 有點亂不好意思 總結一問的話, 就是今天我設計了一個對稱性加密f_k後 下列的自問自答是否正確 Q1: 請問這個算法的破解難易度? A1: 請先告訴我所採用的破解難易度的定義 Q2: 請問這個算法是否只能暴力破解 A2: 目前我這個設計者只想到暴力破解的方式, 但不代表別人或是未來沒有破解法 (請給我"只能暴力破解"的定義?) Q3: 加密算法越複雜破解難度越高, 像是xor一定比AES更容易破解? A3: 不一定, 因為: (1) 算法設計複雜有可能未來某一天可以化簡成簡單的數學形式 (2) 算法設計複雜有可能未來找到快速的演算法破解 (3) 算法設計複雜有可能白做工, 像是Σ_{k=1~N} (-1)^k 或者可以說, 我最初就是因為這些QA才去查資料 結果查出一堆有幫助但是好像不是正面回答QA的資料(其他密碼學定義/詞彙blabla) 還是說因為我這些QA確實都是case by case的實務問題, 難以窮舉全部 所以密碼學為了抽象與一致化才會去下各種定義... 問題有點多, 不好意思@@ 先謝謝回答了~^^
→
05/03 02:26, 2年前 , 38F
Q2:我記得AES-128可以壓到2^126 所以嚴格上不算只能
05/03 02:26, 38F
→
05/03 02:28, 2年前 , 39F
暴力破解 Q3:的確有可能，我們假設他安全就是因為過
05/03 02:28, 39F
→
05/03 02:29, 2年前 , 40F
這麼久了都沒有人能破 像現在正在選後量子密碼標準
05/03 02:29, 40F
→
05/03 02:30, 2年前 , 41F
也是讓大家公開來攻擊 沒人能破就假設他是安全的
05/03 02:30, 41F
嗨int大, 以上覺得認同! 我就是認為無法窮舉出這世界上所有的破解法 又或是說目前沒有模型跟定義去規範所有的"破解法": for any cracking method€set of all cracking methods 所以現有加密法都僅限於"迄今"無破解法
→
05/03 02:31, 2年前 , 42F
然後數學定義上的安全的對稱式加密通常是這樣：
05/03 02:31, 42F
→
05/03 02:33, 2年前 , 43F
攻擊者有1/2會拿到黑箱的f_k,f_k^-1 有1/2會拿到真
05/03 02:33, 43F
→
05/03 02:34, 2年前 , 44F
正隨機的permutation F,F^-1 然後攻擊者可以隨便選
05/03 02:34, 44F
→
05/03 02:35, 2年前 , 45F
input餵給他拿到的function 試到他高興為止 然後攻
05/03 02:35, 45F
→
05/03 02:36, 2年前 , 46F
擊者要回答他拿到的是某個f_k,f_k^-1或是F,F^-1 如
05/03 02:36, 46F
→
05/03 02:37, 2年前 , 47F
果對所有的攻擊者 答對的機率都只比1/2高一個可忽略
05/03 02:37, 47F
→
05/03 02:38, 2年前 , 48F
的值 就說他是Strong Pseudorandom Permutation
05/03 02:38, 48F
→
05/03 02:44, 2年前 , 49F
n個bit的permutation有2^n!種 有趣的地方就在於key
05/03 02:44, 49F
→
05/03 02:47, 2年前 , 50F
只有2^k種 卻可以讓攻擊者沒辦法(在多項式時間內)分
05/03 02:47, 50F
→
05/03 02:48, 2年前 , 51F
辨出兩者的區別
05/03 02:48, 51F
這部分分享想請問一下, 是指所有的對稱性加密都能"化約"成這種討論模式嗎? 以我的"f_k(x) := x xor k"為例, 攻擊者只能拿到output y = f_k(x)而已 我不理解這中間存在什麼黑箱的f_k, f_k^-1以及什麼F, F^-1 還是說這些詞彙還要基於某些"攻擊者能拿到什麼資訊"的假設? 在我的例子中, 攻擊者只能拿到y, 無法拿到我的f_k, 所以他永遠不知道我的k是什麼 ※ 編輯: znmkhxrw (61.231.69.250 臺灣), 05/03/2022 13:38:32
‣ 更多 znmkhxrw 的文章
文章代碼(AID): #1YRbH9Mj (Math)