2014-11-02 100 views
-1

我想破解XOR重複密鑰,我現在沒有關於密鑰和消息的任何內容,只有我知道它使用的是重複密鑰。使用重複鍵XOR加密編碼後的消息sbasebase64'd,因此我首先將base 64轉換爲base16,這樣更容易。我有指示,但我不明白這很好。破解XOR重複密鑰

  1. 設KEYSIZE爲密鑰的猜測長度;嘗試從2到(說)40的值。 編寫一個函數來計算兩個字符串之間的編輯距離/漢明距離。

  2. 對於每個KEYSIZE,取第一個KEYSIZE字節值和第二個KEYSIZE字節值,並找出它們之間的編輯距離。通過除以KEYSIZE標準化這個結果。

  3. 具有最小歸一化編輯距離的鍵可能是關鍵。你可以用最小的2-3個KEYSIZE值進行處理。或者取4個KEYSIZE塊而不是2個平均距離。

現在你可能知道密鑰長度:破密文成密鑰大小長度等的塊,我這剩下的精,就目前而言,我現在正是當我發現如果這是好的,嘗試解碼..

我用Python寫了一個代碼,這一點,它是工作,但我不能完全肯定,如果我這樣做了正確

def compute_distance(str1,str2,keysize): 
     count=0 
     str1=str1.replace("\n", "") 
     str2=str2.replace("\n", "") 
     keysize=str(keysize*8) 
     sbin1=format(int(str1,16),'0'+keysize+'b') 
     sbin2=format(int(str2,16),'0'+keysize+'b') 

     for c1,c2 in zip(sbin1, sbin2): 
     if c1!=c2: 
      count+=1 

     return count 


    def keysize_dist(filelocation): 
     f=open(filelocation,'r') 
     lines=[] 
     for line in f.readlines(): 
     line=line.strip('\n') 
     lines.append(line) 
     lines=''.join(lines).strip('\n') 
     normalized=[] 
     for keysize in range(2,40): 
     count=compute_distance(lines[0:keysize*2],lines[keysize*2:keysize*4],keysize) 

     normalized.append(float(count)/keysize) 


     return lines,int(min(normalized)) 
+0

如果工作正常,您爲什麼認爲自己沒有做到正確? – 2014-11-02 08:41:09

+0

由於最小標準化距離是爲大小5,我沒有成功解碼wih keysize 5 .. – 2014-11-02 08:42:44

+1

因此,那麼它不工作... – 2014-11-02 08:43:29

回答

1

這是方式,我從您的文章的理解。 我做了一個python程序,用循環鍵生成加密xor流,並嘗試應用hamming字符串距離歸一化方法來查找最佳潛在循環密鑰大小。 我不把東西轉換成base64,我直接應用字符串距離而不是二進制距離。

#!/usr/bin/python 

import sys 
from itertools import cycle 

def xor_file_with_cycling_strkey(filelocation,outfile,key): 
    print filelocation 
    f=open(filelocation,'r') 
    f2=open(outfile,'w') 
    lines=[] 
    text=f.read() 
    if text != '': 
    for c,k in zip(text,cycle(key)): 
     r=chr(ord(c)^ord(k)) 
     f2.write(r) 
    f2.close() 
    f.close() 

# not used here, see compute_distance_char based on same idea. 
def compute_distance(str1,str2,keysize): 
    count=0 
    print '%s %s' % (str1,str2) 
    str1=str1.replace("\n", "") 
    str2=str2.replace("\n", "") 
    keysize=str(keysize*8) 
    sbin1=format(int(str1,16),'0'+keysize+'b') 
    sbin2=format(int(str2,16),'0'+keysize+'b') 
    return hamming_distance_str(sbin1,sbin2) 

#do preferer hamming_distance_bin which quicker. 
def compute_distance_char(str1,str2,keysize): 
    count=0 
    str1=str1.replace("\n", "") 
    str2=str2.replace("\n", "") 
    keysize=str(keysize*8) 
    sbin1='' 
    sbin2='' 
    for c in str1: 
    sbin1=sbin1 + format(ord(c),'0'+keysize+'b') 
    for c in str2: 
    sbin2=sbin2 + format(ord(c),'0'+keysize+'b') 
    return hamming_distance_str(sbin1,sbin2) 

def hamming_distance_str(str1,str2): 
    count=0 
    for c1,c2 in zip(str1, str2): 
    if c1!=c2: 
     count+=1 
    return count 

def hamming_distance_bin(str1,str2): 
    count=0 
    for c1,c2 in zip(str1, str2): 
    if c1!=c2: 
     # quick hamming distance, counting number of differing bits. 
     s=ord(c1)^ord(c2) 
     # count number of bits sets using Wegner algorithm 
     while s !=0: 
     s&=(s-1); 
     count+=1 
    return count 

def keysize_dist(filelocation): 
    potential_keysize=0 
    min_dist=40.0 
    f=open(filelocation,'r') 
    lines=[] 
    for line in f.readlines(): 
    line=line.strip('\n') 
    lines.append(line) 
    lines=''.join(lines).strip('\n') 
    normalized=[] 
    for keysize in range(2,40): 
# should first create base16 entries for that one , then don't use it : count_bin1=compute_distance(lines[0:keysize*2],lines[keysize*2:keysize*4],keysize) 
    # proof that both functions compute same value : 
    count_bin1=compute_distance_char(lines[0:keysize*2],lines[keysize*2:keysize*4],keysize) 
    count_bin2=hamming_distance_bin(lines[0:keysize*2],lines[keysize*2:keysize*4]) 
    if (count_bin1 != count_bin2): 
     print 'Discrepency between compute_distance_char->%i and hamming_distance_bin->%i' % (count_bin1,count_bin2) 
    count=hamming_distance_str(lines[0:keysize*2],lines[keysize*2:keysize*4]) 

    normalized_distance=float(count)/keysize 
    print '%s %f' % (keysize,normalized_distance) 
    if (normalized_distance < min_dist): 
     potential_keysize=keysize 
     min_dist=normalized_distance 
# we are more interested in keysize corresponding to minimal distance, tha n to minimal distance itself. 
    return potential_keysize,min_dist 

def main(args=sys.argv): 
if (len(args) < 2): 
    print 'Please enter cleartext origin file to be ciphered then checked an optionaly a key string (max length 40)' 
    return 1 
if (len(args) > 2): 
    key=args[2] 
else: 
    # on purpose default to key with a KEYSIZE char length 5. 
    key='12345' 
xor_file_with_cycling_strkey(args[1],args[1]+'.ciphered',key) 
xor_file_with_cycling_strkey(args[1]+'.ciphered',args[1] + '.cleartext',key) 

# raw non base64 encoded. 
print keysize_dist(args[1] + '.ciphered') 

if __name__ == "__main__": 
    main() 

通過該代碼,您可以獲得完全解決問題所需的所有輸入。

./hamming_detect_xor_cycle.py明文123456789ABCDE ... (14,1.7857142857142858)

它不正確地檢測到所有的大小,但我認爲這是一個統計效果,取決於明文本身可以循環屬性。正如你的主題所說:使用更多的塊可以提供更好的結果。

+0

我不知道爲什麼xor_file_with_cycling_strkey返回t,它只是一個空字符串,它沒有改變,所以爲什麼要返回它? 當我沒有明確的字符串時,真的可以使用字符串距離,我已經將字符串編碼爲十六進制字符,或者它與我有明確的字符串相同? – 2014-11-02 11:34:20

+1

將你的base64解碼成加密字符流中的密文,然後在其上應用str char distance。我用二進制距離測試它,它比str/char差。我在這裏添加了一個更快的二進制實現,比使用格式()和漢明結果字符串。 – 2014-11-02 12:37:03

+0

我真的很感謝:) 關於xor_file_with_cycling_strkey的一個問題。如果我是對的,如果我們不知道密鑰,我們實際上並不需要這個功能?換句話說,如果我已經理解了你的程序,它首先對字符串進行編碼,然後用給定的密鑰對它進行解碼,然後計算距離以檢查它是否正常工作。我對嗎? – 2014-11-02 13:02:29