The Cryptopals Crypto Challenges 解题报告（2）

def PKCS7padding(string, length):
    psize = length - len(string)
    pad = [psize] * psize
    return string + bytelist_to_str(pad)

def removePKCS7padding(string):
    padnum = ord(string[len(string) - 1])
    return string[ : len(string) - padnum]

string="YELLOW SUBMARINE"
paddingstring=PKCS7padding(string,20)
print paddingstring
print removePKCS7padding(paddingstring)

def aes_cbc_encrypt(key, iv, string):
    pnum = (len(string) / 16 + 1) * 16
    paddingString = PKCS7padding(string, pnum)
    ciphertext = ""
    for i in range(pnum / 16):
        block = str_to_bytelist(paddingString[i * 16 : i * 16 + 16])
        xorBlock = bytelist_to_str(xor(block, iv))
        encryptBlock = aes_ecb_encrypt(key, xorBlock)
        ciphertext += encryptBlock
        iv = str_to_bytelist(encryptBlock)
    return ciphertext

def aes_cbc_decrypt(key, iv, string):
    plaintext = ""
    for i in range(len(string) / 16):
        block = aes_ecb_decrypt(key, string[i * 16 : i * 16 + 16])
        xorBlock = xor(str_to_bytelist(block), iv)
        decryptBlock = bytelist_to_str(xorBlock)
        plaintext += decryptBlock
        iv = str_to_bytelist(string[i * 16 : i * 16 + 16])
    return plaintext

f = open('challenge10.txt', 'r')
s = f.read()
ciphertext = base64.b64decode(s)
key = "YELLOW SUBMARINE"
iv = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
plaintext = aes_cbc_decrypt(key, iv, ciphertext)
plaintext = removePKCS7padding(plaintext) #去掉明文末尾的填充
print plaintext

def generate_randomdata(length):
    data = []
    for i in range(length):
        data.append(random.randint(0, 255))
    return data

def random_encrypt(key,iv,string):
    flag = random.randint(1, 2)
    randomFront=bytelist_to_str(generate_randomdata(random.randint(5, 10)))
    randomBack = bytelist_to_str(generate_randomdata(random.randint(5, 10)))
    padRandomString = PKCS7padding(randomFront + string + randomBack)
    print flag
    if flag == 1:#ECB MODE
        ciphertext = aes_ecb_encrypt(key, padRandomString)
    else:#CBC MODE
        ciphertext = aes_cbc_encrypt(key, iv, padRandomString)
    return ciphertext

def detect_mode(ciphertext):
    blocks = [b for b in chunks(ciphertext,16)]
    detects = []
    for b in blocks:
        if blocks.count(b) > 1:
            detects.append(b)
    if detects:
        print("ECB MODE detected!")

key=bytelist_to_str(generate_randomdata(16))
iv=generate_randomdata(16)
string="I have a dream that one day every valley shall be exalted, and every hill and mountain shall be made low, the rough places will be made plain, and the crooked places will be made straight; and the glory of the Lord shall be revealed and all flesh shall see it together." * 10
ciphertext = random_encrypt(key, iv, string)
detect_mode(ciphertext)

Um9sbGluJyBpbiBteSA1LjAKV2l0aCBteSByYWctdG9wIGRvd24gc28gbXkg
aGFpciBjYW4gYmxvdwpUaGUgZ2lybGllcyBvbiBzdGFuZGJ5IHdhdmluZyBq
dXN0IHRvIHNheSBoaQpEaWQgeW91IHN0b3A/IE5vLCBJIGp1c3QgZHJvdmUg
YnkK

unknownString = base64.b64decode("Um9sbGluJyBpbiBteSA1LjAKV2l0aCBteSByYWctdG9wIGRvd24gc28gbXkgaGFpciBjYW4gYmxvdwpUaGUgZ2lybGllcyBvbiBzdGFuZGJ5IHdhdmluZyBqdXN0IHRvIHNheSBoaQpEaWQgeW91IHN0b3A/IE5vLCBJIGp1c3QgZHJvdmUgYnkK")
key = bytelist_to_str(generate_randomdata(16))
def encrypt(string):
    plaintext = bytelist_to_str(string) + unknownString
    ciphertext = aes_ecb_encrypt(key, PKCS7padding(plaintext))
    return str_to_bytelist(ciphertext)

def detect_blocksize():
    ulen = len(encrypt([]))
    p1 = p2 = ''
    l1 = l2 = ulen
    while l1 == l2:
        p1 += 'A'
        l2 = len(encrypt(str_to_bytelist(p1)))
    l1 = l2
    while l1 == l2:
        p2 += 'A'
        l2 = len(encrypt(str_to_bytelist(p1 + p2)))
    #返回：unknown-string长度，填充长度，加密块大小
    return (ulen - (len(p1) - 1), len(p1) - 1, len(p2))

def generate_ciphertexts(buffer):#生成不同字符加密后的字典
    buffers = {}
    for b in range(256):
        buffers[b] = encrypt(buffer + [b])
    return buffers.items()

def guess_bytes(ulen, blocksize):
    buffer = [0x41] * (blocksize-1)
    count = 0
    recoveredBytes = []
    for i in range(ulen):
        if len(recoveredBytes) > 0 and len(recoveredBytes) % blocksize == 0:
            count += 1
            buffer.extend([0x41] * blocksize)
        ciphertexts = generate_ciphertexts(buffer[len(recoveredBytes):] + recoveredBytes)
        ciphertext = [c for c in chunks(encrypt(buffer[len(recoveredBytes):]), blocksize)][count]
        for b, cipher in ciphertexts:
            if [c for c in chunks(cipher, blocksize)][count] == ciphertext:
                recoveredBytes.append(b)
    return recoveredBytes

l, _, blocksize=detect_blocksize()
unknown_str = bytelist_to_str(guess_bytes(l, blocksize))
print removePKCS7padding(unknown_str)

函数profile_for:
profile_for("foo@bar.com")产生以下
{
  email: 'foo@bar.com',
  uid: 10,
  role: 'user'
}
编码为 email=foo@bar.com&uid=10&role=user

key = bytelist_to_str(generate_randomdata(16))
def profile_for(string):
    string.replace('&','_')
    string.replace('=','_')
    return 'email=' + string + '&uid=10&role=user'

def parse_string(string):
    account = {}
    parts = string.split('&')
    for kv in parts:
        k,v = kv.split('=')
        account[k] = v
    return account

def attack():
    admintext = profile_for('A'*10 + 'admin' + '\x0b'*0xb)
    adminCiphertext = aes_ecb_encrypt(key, PKCS7padding(admintext))
    adminBlock = adminCiphertext[16:32]
    #明文为‘email=AAAAAAAAAAadmin\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b’
    #在第二个块中包括admin加密后的结果

    plaintext = profile_for("admin1@me.com")#长度为36
    ciphertext = aes_ecb_encrypt(key, PKCS7padding(plaintext))
    adminCipher = cipher[:-16] + adminBlock
    #为“email=admin1@me.com&uid=10&role=admin\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b”加密后的密文，填充刚好为\x0b
    adminplain = aes_ecb_decrypt(key, admincipher)#role=admin
    print plaintext
    print adminplain

attack()

unknownString = base64.b64decode("Um9sbGluJyBpbiBteSA1LjAKV2l0aCBteSByYWctdG9wIGRvd24gc28gbXkgaGFpciBjYW4gYmxvdwpUaGUgZ2lybGllcyBvbiBzdGFuZGJ5IHdhdmluZyBqdXN0IHRvIHNheSBoaQpEaWQgeW91IHN0b3A/IE5vLCBJIGp1c3QgZHJvdmUgYnkK")
key = bytelist_to_str(generate_randomdata(16))
randomPrefix = bytelist_to_str(generate_randomdata(random.randint(2, 32)))
def encrypt(string):
    plaintext = randomPrefix + bytelist_to_str(string) + unknownString
    ciphertext = aes_ecb_encrypt(key, PKCS7padding(plaintext))
    return str_to_bytelist(ciphertext)

def detect_blocksize():
    ruplen = len(encrypt([]))
    p1 = p2 = ''
    l1 = l2 = ruplen
    while l1 == l2:
        p1 += 'A'
        l2 = len(encrypt(str_to_bytelist(p1)))
    l1 = l2
    while l1 == l2:
        p2 += 'A'
        l2 = len(encrypt(str_to_bytelist(p1 + p2)))
    paddinglen = len(p1) - 1 #对于random-prefix+target-bytes的填充长度
    blocksize = len(p2)
    rulen = ruplen - paddinglen #random-prefix+target-bytes的长度

    #先加密两个块大小的buf，然后其中不断添加元素，直至在密文中可以得到两个相同的块，则对于单独random-prefix字符串的填充长度为len(buf)-blocksize*2
    buf = [0x41] * blocksize * 2
    flag = False
    while not flag and len(buf) < blocksize * 3:
        ciphertext = encrypt(buf)
        ctBlock = [c for c in chunks(ciphertext, blocksize)]
        for i in range(len(ctBlock) - 1):
            if ctBlock[i] == ctBlock[i + 1]:
                flag = True
        if not flag:
            buf += [0x41]
    rpadlen = len(buf) - blocksize * 2 #只有random-prefix的填充长度

    #加密三个块大小的buf，求出两个相同块的位置offset，则前面为random-prefix及填充
    offset = 0
    buf = [0x41]*blocksize*3
    ciphertext = encrypt(buf)
    cBlock = [c for c in chunks(ciphertext, blocksize)]
    for i in range(len(cBlock) - 1):
        if cBlock[i] == cBlock[i + 1]:
            offset = i
            break
    randomprefixlen = offset * blocksize - rpadlen #random-prefix长度
    #返回：random-prefix长度，target-bytes长度，加密块大小
    return (randomprefixlen, ruplen - paddinglen - randomprefixlen, blocksize)

def generate_ciphertexts(buffer):
    buffers = {}
    for b in range(256):
        buffers[b] = encrypt(buffer + [b])
    return buffers.items()

def guess_bytes(randomprefixlen, ulen, blocksize):
    buffer = [0x41] * (blocksize - randomprefixlen % blocksize + blocksize - 1)
    count = randomprefixlen / blocksize + 1
    recoveredBytes = []
    for i in range(ulen):
        if len(recoveredBytes) > 0 and len(recoveredBytes) % blocksize == 0:
            count += 1
            buffer.extend([0x41] * blocksize)
        ciphertexts = generate_ciphertexts(buffer[len(recoveredBytes):] + recoveredBytes)
        ciphertext = [c for c in chunks(encrypt(buffer[len(recoveredBytes):]), blocksize)][count]
        for b, cipher in ciphertexts:
            if [c for c in chunks(cipher, blocksize)][count] == ciphertext:
                recoveredBytes.append(b)
    return recoveredBytes

rlen, ulen, blocksize = detect_blocksize()
unknown_str = bytelist_to_str(guess_bytes(rlen, ulen, blocksize))
print removePKCS7padding(unknown_str)

def checkPKCS7padding(string):
    l = len(string)
    c = string[l-1]
    paddingCount = ord(c)
    for i in range(paddingCount):
        if string[l-1-i] != c:
            print "PKCS7padding invalid!"
            return False
    print "check ok!"
    return True

string1="ICE ICE BABY\x04\x04\x04\x04"
checkPKCS7padding(string1)
string2="ICE ICE BABY\x05\x05\x05\x05"
checkPKCS7padding(string2)
string3="ICE ICE BABY\x01\x02\x03\x04"
checkPKCS7padding(string3)

key = bytelist_to_str(generate_randomdata(16))
iv = generate_randomdata(16)
def profile_for(string):
    string = string.replace(';', '_')
    string = string.replace('=', '_')
    return "comment1=cooking%20MCs;userdata=" + string + ";comment2=%20like%20a%20pound%20of%20bacon"

def parse_string(string):
    account = {}
    part = string.split(';')
    for kv in part:
        try:
            k,v = kv.split('=',1)
        except:
            k = kv
            v = ''
        account[k] = v
    return account

def encrypt(string):
    plaintext = profile_for(string)
    return aes_cbc_encrypt(key, iv, PKCS7padding(plaintext))

def decrypt(ciphertext):
    plaintext = aes_cbc_decrypt(key, iv, ciphertext)
    return parse_string(plaintext)

def attack():
    adminPlain = ";admin=true"
    #comment1=cooking%20MCs;userdata=_admin_true;comment2=%20like%20a%20pound%20of%20bacon
    ciphertext = encrypt(adminPlain)
    adminCipher = str_to_bytelist(ciphertext)
    #第一个'_'下标为32，CBC通过更改前一个块的对应内容即下标16，来更改'_'
    #第二个'_'下标为38，前一个块对应下标为22
    adminCipher[16] = adminCipher[16] ^ ord('_') ^ ord(';')
    adminCipher[22] = adminCipher[22] ^ ord('_') ^ ord('=')
    plaintext = decrypt(bytelist_to_str(adminCipher))
    print decrypt(ciphertext)
    print plaintext

attack()