→ int0x80 : 你xor的例子就是one-time-pad k得和明文一樣長05/01 20:41
→ int0x80 : 而且只能用一次05/01 20:41
→ int0x80 : AES的key是固定大小 而且可以用很多次 甚至可以讓攻05/01 20:44
→ int0x80 : 擊者拿到f_k,f_k^-1 然後還是不知道k是什麼05/01 20:46
→ int0x80 : 可以看一下Pseudorandom Functions05/01 20:50
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
我有少考慮到什麼嗎?
推 isaswa : google: information theoretic security05/01 22:20
看wiki好像在敘述一些"因為訊息不足, 即便時間無限也永遠無法被破解"的加密算法
但是我從接觸加密相關的資料以來, 每一種方法如果目前仍在用, 都是可以暴力破解的
只是時間如果長到誇張就歸納為現在無法破解
想額外問一下, 有對於"可/不可破解"的數學定義或是實務定義嗎?
數學定義之前是看過一些用"機率加運算時間"的定義方式
而實務定義的話, 是否只能說"到目前為止只能用暴力破解"來當不可破解的定義?
只是不排除未來某一天有人剛好想到很快的演算法, 或是猜到key, 或是簡化出數學式
舉例來說, Σ_{k=1~N} (-1)^k 的答案是多少, 當N=2^1000時
我聲稱這個在數十年電腦都跑不完(無法暴力破解)
但是任何一個小學生都能告訴這個答案是多少(簡化數學式了)
我這個例子是想表達是否實務上的加密方式都有這個危險, 只是目前沒發生而已?
(然後information theoretic security就是說這件事絕對不能發生, 即無解)
※ 編輯: znmkhxrw (59.102.225.191 臺灣), 05/02/2022 02:13:22
推 cplalexandta: 你舉的XOR加密的例子基本上有n個獨立sample的話用高05/02 07:21
→ cplalexandta: 斯消去就有高機率可以反推k了05/02 07:21
c大你應該是指如果對方有f_k的程式, 那這樣當然別人隨便一個input輸入後就知道k是什
麼了
可是我的意思是對方只知道我的y, 而y是我自己由某個f_k產生的, 即便讓他知道f_k的設
計只是跟某個k做xor, 他也猜不到這個k是什麼
推 cplalexandta: Information theoretic secure的要求會imply就算你05/02 07:24
→ cplalexandta: 有一堆sample也沒辦法反推密鑰05/02 07:24
推 cplalexandta: 然後加密安全性也不是只有information theoretic se05/02 07:27
→ cplalexandta: cure這個定義 密碼學研究據我所知更常用的是類似pol05/02 07:27
→ cplalexandta: ynomial time indistinguishable之類的標準 05/02 07:27
這應該就是我看到的用機率測度加上時間複雜度所下的定義了
推 LPH66 : 說起來你有去查「one time pad」這個名詞了嗎? 05/02 07:51
→ LPH66 : 你最一開始提的 XOR 做法就是這個05/02 07:52
→ LPH66 : 而且確實有人證明了 (那位大名鼎鼎的 Shannon) 說05/02 07:52
→ LPH66 : 只要 one time pad 的鑰匙至少跟訊息一樣長05/02 07:52
→ LPH66 : 且每次都重新產生不重覆使用, 那它是最安全的密碼05/02 07:53
→ LPH66 : 但是實務加密上我們還有鑰匙分送問題及應用效率問題 05/02 07:54
→ LPH66 : 你要傳一個訊息還要傳一個跟這訊息一樣長的密碼 05/02 07:54
→ LPH66 : 這就算不上是個「安全」的密碼應用了05/02 07:55
→ LPH66 : 現代的密碼應用確實都是在找一些目前認為計算上很難05/02 07:56
→ LPH66 : 的問題放入演算法的核心; 這裡會應用到你應該聽過的05/02 07:56
→ LPH66 : 這也能算是對你的「可/不可破解的數學定義」的回答05/02 08:00
→ LPH66 : 目前認為的「很難破解」基本上就是「要破解它要解 05/02 08:01
→ LPH66 : 一個 NP 完全問題, 但現在一般認為這不能很快做到」 05/02 08:02
嗨L大, 讀了#1GPBcQPe這篇受益良多, 裡面確實還有一個變因是"計算模型"
→ LPH66 : 噢, 回頭看到你在談的是對稱加密...05/02 08:07
→ LPH66 : 這方面的話, 有一個關鍵字是「Feistel Cipher」05/02 08:07
→ LPH66 : 現在大多數的對稱加密的架構都是這個東西05/02 08:07
→ LPH66 : 這是因為它也有理論證明只要當中的單輪計算符合05/02 08:08
→ LPH66 : 某些條件的話, 那全部計算結果就具有某個計算強度在05/02 08:08
→ LPH66 : 你的問題可以去研究這東西跟它的安全性證明05/02 08:09
→ LPH66 : 各種不同的對稱加密就是單輪計算的設計不一樣而已05/02 08:10
→ LPH66 : 因此對於這些對稱加密的演算法的破解也就會專注在 05/02 08:11
→ LPH66 : 破解所設計的單輪運算, 看能不能強迫造成什麼性質 05/02 08:11
→ LPH66 : 使其得以推算出中間結果甚至密鑰05/02 08:11
這些關鍵字以我現有的密碼學知識來說有點難串起來...
有點像是讀了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的實務問題, 難以窮舉全部
所以密碼學為了抽象與一致化才會去下各種定義...
問題有點多, 不好意思@@
先謝謝回答了~^^
→ int0x80 : Q2:我記得AES-128可以壓到2^126 所以嚴格上不算只能 05/03 02:26
→ int0x80 : 暴力破解 Q3:的確有可能，我們假設他安全就是因為過 05/03 02:28
→ int0x80 : 這麼久了都沒有人能破 像現在正在選後量子密碼標準 05/03 02:29
→ int0x80 : 也是讓大家公開來攻擊 沒人能破就假設他是安全的 05/03 02:30
嗨int大, 以上覺得認同! 我就是認為無法窮舉出這世界上所有的破解法
又或是說目前沒有模型跟定義去規範所有的"破解法":
for any cracking method€set of all cracking methods
所以現有加密法都僅限於"迄今"無破解法
→ int0x80 : 然後數學定義上的安全的對稱式加密通常是這樣： 05/03 02:31
→ int0x80 : 攻擊者有1/2會拿到黑箱的f_k,f_k^-1 有1/2會拿到真 05/03 02:33
→ int0x80 : 正隨機的permutation F,F^-1 然後攻擊者可以隨便選 05/03 02:34
→ int0x80 : input餵給他拿到的function 試到他高興為止 然後攻 05/03 02:35
→ int0x80 : 擊者要回答他拿到的是某個f_k,f_k^-1或是F,F^-1 如 05/03 02:36
→ int0x80 : 果對所有的攻擊者 答對的機率都只比1/2高一個可忽略 05/03 02:37
→ int0x80 : 的值 就說他是Strong Pseudorandom Permutation 05/03 02:38
→ int0x80 : n個bit的permutation有2^n!種 有趣的地方就在於key 05/03 02:44
→ int0x80 : 只有2^k種 卻可以讓攻擊者沒辦法(在多項式時間內)分 05/03 02:47
→ int0x80 : 辨出兩者的區別 05/03 02:48
這部分分享想請問一下, 是指所有的對稱性加密都能"化約"成這種討論模式嗎?
以我的"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