Welcome to the Crypto Series again. Last time we learned something about peculiarities in AES in CBC mode. Today we will continue solving Cryptopals Challenges, this time related to CTR mode of AES algorithm. But some theory first!
CTR mode
AES in Counter (CTR) mode is quite special. Unlike modes discussed previously, with this mode we can use AES as stream cipher. Encryption and decryption routines are equivalent, as shown in the diagram:
To get a keystream, you encrypt Nonce (similar to IV) concatenated with block counter under a key. AES routine will yield keystream in 16-byte blocks, but you generally use only bytes of your plaintext length. This effectively turns AES into a stream cipher.
For clarification, see the following example (nonce = 0xdeadbeef, key = ‘YELLOW SUBMARINE’). Notice how nonce and counter are concatenated and that no padding is used.
Nonce;Counter |efbeadde000000000000000000000000|efbeadde000000000100000000000000| Keystream |5f59005d4288baa18a8546f6ee4230bd|9d1bad6e2932f9398b2ee4793ee6c699| Plaintext |L o r e m i p s u m d o l o |r s i t a m e t . Plaintext (hex) |4c6f72656d20697073756d20646f6c6f|722073697420616d65742e Ciphertext |133672382fa8d3d1f9f02bd68a2d5cd2|ef3bde075d129854ee5aca
After keystream generation, the mode is basically a XOR operation between the keystream, plaintext and ciphertext.
CTR detection
Recall that, in ECB mode, change of one bit will affect single block (in both encryption and decryption). In CBC, change of one bit in plaintext will change all following blocks. Change in ciphertext affects current block and corresponding bits of the following block (bitflipping attack). Adding bytes in ECB or CBC will not change the resulting length, except when you overflow the block boundary – in that case 16 bytes will be added.
CTR is different. It does not have to follow the 16B boundary. Change will affect only the corresponding bit, addition or removal of bytes will be reflected precisely.
CTR fixed-nonce attack
Think about the keystream generation process. The counter part has strictly defined pattern – for each use it counts from zero. If you also reuse both key and nonce, you obviously receive same keystream. That is bad – if you know both plaintext and ciphertext of one message, you can instantly compute the used keystream and use it for other secret messages.
If you capture enough ciphertexts, you can retrieve the keystream as well. When we talked about XOR and repeating key back in 0x01, we transposed the blocks of ciphertext to get sets of single-byte-xored data and then apply some frequency analysis. This is essentialy the same case and we will demonstrate it in tasks 3.19 and 3.20.
You can feel the problem by looking at the following equations:
P1 = C1 ^ K
P2 = C2 ^ K | ^ P1
P1 ^ P2 = P1 ^ C2 ^ K
P1 ^ P2 = C1 ^ K ^ C2 ^ K
P1 ^ P2 = C1 ^ C2
This is for 2 ciphertexts only, but you should already feel that P1 ^ P2 will not be that secret anymore. Here is a visual proof:
CTR random access read/write
Usually, if you try to decrypt plaintext or encrypt ciphertext, you end up with garbage. Not with CTR! In fixed-nonce situations or in systems where you include data into an existing ciphertext (e.g. an encrypted drive), you pass ciphertext instead of expected plaintext, and viola – plaintext is revealed. This is what happens in task 4.25.
CTR bitflipping attack
Plaintext and corresponding ciphertext are entangled by the XOR operation, where change of one bit in source changes only one corresponding bit in target. Therefore, with specially crafted ciphertext, one can get arbitraty plaintext. It is similar to CBC bitflipping attack, but in this case we are not limited by blocks anymore.
Assume P’ is desired plaintext and C’ is ciphertext modified by adversary:
P = C ^ K P' = C' ^ K C' = P' ^ K = P' ^ P ^ C
Let’s go practical now.
3.18 – Implement CTR
The implementation is tested here.
*** c = base64:L77na/nrFsKvynd6HzOoG7GHTLXsTVu9qvY/2syLXzhPweyyMTJULu/6/kXX0KSvoOLSFQ== [.] c = /\xbe\xe7k\xf9\xeb\x16\x...\xa4\xaf\xa0\xe2\xd2\x15 *** key = YELLOW SUBMARINE [.] key = YELLOW SUBMARINE *** nonce = 0 [.] nonce = *** aes = AES mode=ctr key=key nonce=nonce ciphertext=c *** p = decrypt aes *** p~Raw Raw: b"Yo, VIP Let's kick it Ice, Ice, baby Ice, Ice, baby " *** aes = AES mode=ctr key=key nonce=nonce plaintext=p *** c2 = encrypt aes *** checksum c c2 c 683ad67b2170f875bbdcc4c05993d09e c2 683ad67b2170f875bbdcc4c05993d09e
3.19, 3.20 – Break fixed-nonce CTR
These tasks are very similar. In the first one you are IMHO expected to do frequency analysis on ciphertexts directly, in the second one you use transposition approach. I came up with sort of a hybrid solution and used it for both tasks.
The task requires to encrypt 40 plaintexts before actual attack can be executed. This will result in ugly bash script I do not want here, so let me skip this part by specifying the ciphertexts directly (key = ‘YELLOW SUBMARINE’, nonce = 0).
*** c00 = base64:P/GjKtnHZo+G2yMpBHauUrOYTL/0AmG777V5s8uPCg== *** c01 = base64:Nb6mIsHFZpWK22t9Gnq1G7bMCr37CGE= *** c02 = base64:MKOkJo/BKZeN22YvTHyxUraJH7e4DH+xob0/9N2LCg== *** c03 = base64:M7isI9vHI4yXxy4+CX23B6CVTLT3GGG7vPQ= *** c04 = base64:P/GjKtnHZpKC3HA4CDO0G6aETL24A32677V5s9uGFjhFxe+v *** c05 = base64:OaPrO8DOL5aGj244DX2qHLWACa/rTWWxvb5svw== *** c06 = base64:OaPrI87UI8KPxm06CWGmFvKNG7TxAXf+rrR7s9yPGnw= *** c07 = base64:Jr6nItvHZo+Gzm00AnSvF6GfTKv3H3at4w== *** c08 = base64:N7+va9vKKZeEx3d9DnalHaCJTJW4BXO6775w/co= *** c09 = base64:ObfrKo/PKYGIxm06TGeiHrfMA664DDK5prh6 *** c10 = base64:Ir7rO8PHJ5GGj2J9D3yuArOCBbP2 *** c11 = base64:N6OkPsHGZpaLyiM7BWGmUrOYTKjwCDK9o699vw== *** c12 = base64:NLSiJciCJYeR22I0AjO3GrOYTKjwCGv+rrR7s+Y= *** c13 = base64:NKS/a8PLMIeHj3Q1CWGmUr+DGLD9FDK3vPpo/N2ASQ== *** c14 = base64:N72na8zKJ4yEymdxTHCrE7yLCbi4GGaqqqhz6pU= *** c15 = base64:N/G/Lt3QL4CPyiM/CXK2BqvMBa+4D32sofQ= *** c16 = base64:IrmqP4/VKY+CwSQuTHeiC6HMG7nqCDKtv79x5w== *** c17 = base64:P7/rIsjMKZCCwXd9C3ysFvKbBbD0QQ== *** c18 = base64:PrS5a8HLIYqX3CM0AjOiALWZAbn2GQ== *** c19 = base64:I7+/IsOCLoeRj3UyBXCmUrWeCau4HnqsprZzvQ== *** c20 = base64:IbmqP4/UKYuAyiMwA2GmUqGbCbnsTWa2rrQ/+8qcAA== *** c21 = base64:IbmuJY/bKZeNyCM8AnfjELeNGajxC2ey4w== *** c22 = base64:Jbmua93NIofD22x9BHKxALuJHq+n *** c23 = base64:IrmiOI/PJ4zDx2I5THimAqbMDfzrDnqxoLY= *** c24 = base64:N7+va93NIofDwHYvTGSqHLWJCPzwAmCtqvQ= *** c25 = base64:IrmiOI/NMoqG3SM1BWDjGreAHLnqTXOwq/p54caLHXw= *** c26 = base64:IbC4a8zNK4uNyCM0AmesUrqFH/z+AmC9quE= *** c27 = base64:PrTrJsbFLpbDx2IrCTO0HbzMCr31CDK3ofpr+8rOFnZJjA== *** c28 = base64:Jb7rOMrMNYuXxnU4THuqAfKCDajtH3f+vL96/sqKXw== *** c29 = base64:Jb7rL87QL4yEj2IzCDOwBbeJGPzwBGH+u7Jw5siGBzY= *** c30 = base64:IrmiOI/NMoqG3SMwDX3jO/KEDbi4CWC7rrd69w== *** c31 = base64:N/GvOdrMLYeNgyMrDXqtX7WAA67xAmet77Zw5tvA *** c32 = base64:PrTrI87GZoaMwWZ9AXywBvKOBajsCGD+uKhw/cg= *** c33 = base64:Ir7rOMDPI8KUx2x9DWGmUryJDa64AGv+p79+4dvC *** c34 = base64:L7S/a+aCKJeOzWYvTHuqH/KFAvzsBXf+vLVx9JQ= *** c35 = base64:PrTna9vNKc7Dx2IuTGGmAbuLArn8TXq3vPpv8t2a *** c36 = base64:P7/rP8fHZoGC3HY8ADOgHb+JCKWj *** c37 = base64:PrTna9vNKc7Dx2IuTHGmF7zMD7T5A3W7q/p2/Y+GGmsN1Pu5f1c= *** c38 = base64:IqOqJdzEKZCOymd9GWe3F6CAFeY= *** c39 = base64:N/G/Lt3QL4CPyiM/CXK2BqvMBa+4D32sofQ= *** x = ctr-fixed-nonce c00 c01 c02 c03 c04 c05 c06 c07 c08 c09 c10 c11 c12 c13 c14 c15 c16 c17 c18 c19 c20 c21 c22 c23 c24 c25 c26 c27 c28 c29 c30 c31 c32 c33 c34 c35 c36 c37 c38 c39 english [.] Revealed XOR value: V\xd1\xebK\xaf\xa2F\xe2\xe3\xaf#]l\x13\xc3r\xd2\xecl\xdc
You can validate results like this:
*** x.ciphertext = c00 *** p = decrypt x *** p~Raw Raw: b'i Have met\x00them at c\xa2\xd3\x8a\xf0@\x17?Q( )'
The ctr-fixed-nonce command returns XOR object – holding plaintext, ciphertext and keystream. As in 0x01, you can attempt to manually alter plaintext with edit x.plaintext and key will be adjusted accordingly. Unfortunately, the keystream will not make sense and will not be repeated, so from this point it is just trial-and-error.
4.25 – Break random access read/write
For this mission we need to compose an oracle. In real situation (encrypted drive) the oracle would attempt to push the plaintext through drive’s encryption routines into a fixed position on the drive and then read the data back. In the task the oracle will simply take provided data (any format), encrypt it under a static key and nonce and return ciphertext as raw bytestring. Next we prepare the initial ciphertext we will later try to reveal:
*** key = YELLOW SUBMARINE *** nonce = 0 [.] nonce = *** p = file:/etc/passwd [.] p = root:x:0:0:root:/root:/b...stent:/usr/sbin/nologin\n *** aes = AES mode=ctr key=key nonce=nonce plaintext=p *** c = encrypt aes
Now we will try to “overwrite the data on the drive” with new plaintext, but actually we will use the unexpected ciphertext instead. XOR properties will take care of the rest.
*** o = oracle oracles/cp_25.py *** p = c *** result = run o p *** hd result 00000000 726f 6f74 3a78 3a30 3a30 3a72 6f6f 743a |root:x:0:0:root:| 00000010 2f72 6f6f 743a 2f62 696e 2f62 6173 680a |/root:/bin/bash.| 00000020 6461 656d 6f6e 3a78 3a31 3a31 3a64 6165 |daemon:x:1:1:dae| ...
4.26 – CTR bitflipping
Two oracles will be needed. The encryption oracle encrypts message in the form cooking%20MCs;userdata=…;comment2=%20like%%20a%20pound%20of%20bacon
where userdata is provided by user in any format and it is sanitized. Ciphertext in raw bytestring format is returned. The second oracle just decrypts given ciphertext (any format) and returns raw bytestring. Then you run ctr-bitflipping command, providing offset and payload to be placed instead.
*** enc = oracle oracles/cp_26_e.py *** dec = oracle oracles/cp_26_d.py *** *** offset = 3 [.] offset = 3 *** payload = ';admin=true;' [.] payload = ;admin=true; *** x = ctr-bitflipping enc dec offset payload [.] Trying sample payload. [.] Payload: b'thisishalloween' [.] Decrypted: b'cooking%20MCs;userdata=thisishalloween;comment2=%20like%20a%20pound%20of%20bacon' [.] Bitflipping... *** x~Raw Raw: b'coo;admin=true;serdata=thisishalloween;comment2=%20like%20a%20pound%20of%20bacon'
Conclusion
This is farewell to the AES algorithm. Later I maybe dive into other modes, but now we will follow Cryptopals curriculum and continue with random number generators. Remember that:
- CTR mode allows AES to be used as stream cipher,
- in CTR encryption and decryption operations are equivalent,
- do not reuse nonce value,
- do not use CTR mode for random access, even though this is supposed benefit,
- you can bitflip again (even better actually) -> use Encrypt-then-MAC approach to validate integrity of ciphertext from foregin source.