Perfect Synchronization
7 minutes to read
We are given the Python source code to encrypt the flag:
from os import urandom
from Crypto.Cipher import AES
from secret import MESSAGE
assert all([x.isupper() or x in '{_} ' for x in MESSAGE])
class Cipher:
def __init__(self):
self.salt = urandom(15)
key = urandom(16)
self.cipher = AES.new(key, AES.MODE_ECB)
def encrypt(self, message):
return [self.cipher.encrypt(c.encode() + self.salt) for c in message]
def main():
cipher = Cipher()
encrypted = cipher.encrypt(MESSAGE)
encrypted = "\n".join([c.hex() for c in encrypted])
with open("output.txt", 'w+') as f:
f.write(encrypted)
if __name__ == "__main__":
main()
And we also have the output of the script (since it is a very large output, it os not completely shown here):
0fbf645baa0ecce12ed52071a4ed0d1d
ce2e2acd1155ac79105dcabcdb4fbbff
d78843699ad962a2a7c513d193d27ab4
9a2f91dbedaa39d9b53f8146c2301098
3ea6ab81fee5f5c718f48b86e8680732
d78843699ad962a2a7c513d193d27ab4
...
a952cfc1d886d6084113d5f3e13508f0
48654fae441fee7cd607d8cb90c1de44
3ea6ab81fee5f5c718f48b86e8680732
ddfdaa01baab48baf54067dd3a3de527
ddfdaa01baab48baf54067dd3a3de527
d3eae0ab73225a3d841241af5d8a0654
d78843699ad962a2a7c513d193d27ab4
Source code analysis
First of all, we know that the message characters are all uppercase letters, underscores, curly brackets or spaces:
assert all([x.isupper() or x in '{_} ' for x in MESSAGE])
Moreover, the encryption function takes a single character, adds a random 15-byte padding and uses AES ECB to encrypt it:
class Cipher:
def __init__(self):
self.salt = urandom(15)
key = urandom(16)
self.cipher = AES.new(key, AES.MODE_ECB)
def encrypt(self, message):
return [self.cipher.encrypt(c.encode() + self.salt) for c in message]
AES ECB
Let’s review how AES ECB works:
The point here is that equal plaintext blocks produce equal ciphertexts blocks. In fact, we have a message that contains at most 30 different characters (uppercase letters plus the underscore, plus the curly brackets plus the space). Therefore, we will have at most 30 different ciphertext blocks, let’s check it out:
$ python3 -q
>>> with open('output.txt') as f:
... cts = f.read().splitlines()
...
>>> len(set(cts))
30
Perfect, as expected.
Solution approach
Since we only have 30 different symbols in the message and thus 30 different ciphertexts, we can apply some frequency analysis plus word guessing (in English) to find letters and fill in the gaps to form words and sentences that make sense.
The first we can do is find the ciphertext blocks for { and } (which will appear just once):
>>> import json
>>> from collections import Counter
>>>
>>> print(json.dumps(Counter(cts), indent=2))
{
"0fbf645baa0ecce12ed52071a4ed0d1d": 31,
"ce2e2acd1155ac79105dcabcdb4fbbff": 89,
"d78843699ad962a2a7c513d193d27ab4": 142,
"9a2f91dbedaa39d9b53f8146c2301098": 7,
"3ea6ab81fee5f5c718f48b86e8680732": 41,
"b403c6f30eec7075d0643b5d4125de1b": 84,
"9e520d83ca02f81ab980ed7ff9a16526": 55,
"9b9233be563be442bf2edf0e3e42848d": 34,
"a952cfc1d886d6084113d5f3e13508f0": 230,
"00273fa04b9b836c553d876502e9a1e2": 101,
"d3eae0ab73225a3d841241af5d8a0654": 61,
"4ca1a8b8e8ca22b70d69ca257d79e5ed": 103,
"98c50ceddda78b850757dc37c1c0814d": 87,
"cb20a26ba8411b2e0072e7438ed67e54": 22,
"4065e6b94c150f4137af46b752e25204": 37,
"495c118c128a67d8a0f022e3f001775e": 75,
"d395fedae9dca912da1b1b50b0aca161": 100,
"c98f7e77e918e98833b8fa19de4b1653": 46,
"e3372f2164f66ea750b5b14f8166b0b9": 23,
"473a4eb8c699b9141c7d0bb4fa691674": 8,
"b1119ba67f26c30144e9cea6a6d7059c": 18,
"a33f02cf75488a76efb91511a0111982": 22,
"48654fae441fee7cd607d8cb90c1de44": 32,
"3321154f7ace2161b8cafb37c6307e6b": 9,
"4fdd58bb71f5f8c882eaa592d51cf647": 5,
"ddfdaa01baab48baf54067dd3a3de527": 8,
"8115f6662bacddd86db1ae8dc533c46c": 2,
"d4dde50295a8c036709603b3c216e44d": 1,
"97038e93767664edf41312c98285ba94": 2,
"25581e56ea570e8f68c9dab82f24f36e": 1
}
So, we know that d4dde50295a8c036709603b3c216e44d and 25581e56ea570e8f68c9dab82f24f36e are the ciphertext blocks for { and }. So, we can guess four more characters ( HTB) in the ciphertext output:
...
9b9233be563be442bf2edf0e3e42848d
a952cfc1d886d6084113d5f3e13508f0 ·
c98f7e77e918e98833b8fa19de4b1653 H
d395fedae9dca912da1b1b50b0aca161 T
cb20a26ba8411b2e0072e7438ed67e54 B
d4dde50295a8c036709603b3c216e44d {
4ca1a8b8e8ca22b70d69ca257d79e5ed
98c50ceddda78b850757dc37c1c0814d
a33f02cf75488a76efb91511a0111982
48654fae441fee7cd607d8cb90c1de44
d3eae0ab73225a3d841241af5d8a0654
d78843699ad962a2a7c513d193d27ab4
97038e93767664edf41312c98285ba94
4ca1a8b8e8ca22b70d69ca257d79e5ed
3ea6ab81fee5f5c718f48b86e8680732
cb20a26ba8411b2e0072e7438ed67e54
4ca1a8b8e8ca22b70d69ca257d79e5ed
d395fedae9dca912da1b1b50b0aca161
98c50ceddda78b850757dc37c1c0814d
d395fedae9dca912da1b1b50b0aca161
3ea6ab81fee5f5c718f48b86e8680732
d395fedae9dca912da1b1b50b0aca161
98c50ceddda78b850757dc37c1c0814d
495c118c128a67d8a0f022e3f001775e
b403c6f30eec7075d0643b5d4125de1b
97038e93767664edf41312c98285ba94
9e520d83ca02f81ab980ed7ff9a16526
98c50ceddda78b850757dc37c1c0814d
48654fae441fee7cd607d8cb90c1de44
c98f7e77e918e98833b8fa19de4b1653
d78843699ad962a2a7c513d193d27ab4
ce2e2acd1155ac79105dcabcdb4fbbff
25581e56ea570e8f68c9dab82f24f36e }
a952cfc1d886d6084113d5f3e13508f0 ·
9e520d83ca02f81ab980ed7ff9a16526
...
In Visual Studio Code or some other text editor, we can select all occurrences for a ciphertext block and append the corresponding plaintext character (· for spaces) in the whole output:
9b9233be563be442bf2edf0e3e42848d
a952cfc1d886d6084113d5f3e13508f0 ·
c98f7e77e918e98833b8fa19de4b1653 H
d395fedae9dca912da1b1b50b0aca161 T
cb20a26ba8411b2e0072e7438ed67e54 B
d4dde50295a8c036709603b3c216e44d {
4ca1a8b8e8ca22b70d69ca257d79e5ed
98c50ceddda78b850757dc37c1c0814d
a33f02cf75488a76efb91511a0111982
48654fae441fee7cd607d8cb90c1de44
d3eae0ab73225a3d841241af5d8a0654
d78843699ad962a2a7c513d193d27ab4
97038e93767664edf41312c98285ba94
4ca1a8b8e8ca22b70d69ca257d79e5ed
3ea6ab81fee5f5c718f48b86e8680732
cb20a26ba8411b2e0072e7438ed67e54 B
4ca1a8b8e8ca22b70d69ca257d79e5ed
d395fedae9dca912da1b1b50b0aca161 T
98c50ceddda78b850757dc37c1c0814d
d395fedae9dca912da1b1b50b0aca161 T
3ea6ab81fee5f5c718f48b86e8680732
d395fedae9dca912da1b1b50b0aca161 T
98c50ceddda78b850757dc37c1c0814d
495c118c128a67d8a0f022e3f001775e
b403c6f30eec7075d0643b5d4125de1b
97038e93767664edf41312c98285ba94
9e520d83ca02f81ab980ed7ff9a16526
98c50ceddda78b850757dc37c1c0814d
48654fae441fee7cd607d8cb90c1de44
c98f7e77e918e98833b8fa19de4b1653 H
d78843699ad962a2a7c513d193d27ab4
ce2e2acd1155ac79105dcabcdb4fbbff
25581e56ea570e8f68c9dab82f24f36e }
a952cfc1d886d6084113d5f3e13508f0 ·
9e520d83ca02f81ab980ed7ff9a16526
Now it’s time to use intuition to guess words. Take a look at this:
4065e6b94c150f4137af46b752e25204
a952cfc1d886d6084113d5f3e13508f0 ·
cb20a26ba8411b2e0072e7438ed67e54 B
9b9233be563be442bf2edf0e3e42848d
a952cfc1d886d6084113d5f3e13508f0 ·
d395fedae9dca912da1b1b50b0aca161 T
c98f7e77e918e98833b8fa19de4b1653 H
d78843699ad962a2a7c513d193d27ab4
a952cfc1d886d6084113d5f3e13508f0 ·
00273fa04b9b836c553d876502e9a1e2
It is pretty obvious that it must be ?·BY·THE·?, so we have the Y and the E.
Then we can find this:
9e520d83ca02f81ab980ed7ff9a16526
d395fedae9dca912da1b1b50b0aca161 T
a952cfc1d886d6084113d5f3e13508f0 ·
d395fedae9dca912da1b1b50b0aca161 T
c98f7e77e918e98833b8fa19de4b1653 H
00273fa04b9b836c553d876502e9a1e2
d395fedae9dca912da1b1b50b0aca161 T
a952cfc1d886d6084113d5f3e13508f0 ·
98c50ceddda78b850757dc37c1c0814d
So, we can have A from ?·THAT·?.
This must be ?·BOTH·THE·B?, so we have the O:
98c50ceddda78b850757dc37c1c0814d
a952cfc1d886d6084113d5f3e13508f0 ·
cb20a26ba8411b2e0072e7438ed67e54 B
495c118c128a67d8a0f022e3f001775e
d395fedae9dca912da1b1b50b0aca161 T
c98f7e77e918e98833b8fa19de4b1653 H
a952cfc1d886d6084113d5f3e13508f0 ·
d395fedae9dca912da1b1b50b0aca161 T
c98f7e77e918e98833b8fa19de4b1653 H
d78843699ad962a2a7c513d193d27ab4 E
a952cfc1d886d6084113d5f3e13508f0 ·
cb20a26ba8411b2e0072e7438ed67e54 B
ce2e2acd1155ac79105dcabcdb4fbbff
This one is a lucky guess for ?E·AND·?:
e3372f2164f66ea750b5b14f8166b0b9
d78843699ad962a2a7c513d193d27ab4 E
a952cfc1d886d6084113d5f3e13508f0 ·
00273fa04b9b836c553d876502e9a1e2 A
b403c6f30eec7075d0643b5d4125de1b
4065e6b94c150f4137af46b752e25204
a952cfc1d886d6084113d5f3e13508f0 ·
4ca1a8b8e8ca22b70d69ca257d79e5ed
Here’s another lucky guess for ·FREQUENCY·ANALYSIS·:
a952cfc1d886d6084113d5f3e13508f0 ·
0fbf645baa0ecce12ed52071a4ed0d1d
ce2e2acd1155ac79105dcabcdb4fbbff
d78843699ad962a2a7c513d193d27ab4 E
9a2f91dbedaa39d9b53f8146c2301098
3ea6ab81fee5f5c718f48b86e8680732
d78843699ad962a2a7c513d193d27ab4 E
b403c6f30eec7075d0643b5d4125de1b N
9e520d83ca02f81ab980ed7ff9a16526
9b9233be563be442bf2edf0e3e42848d Y
a952cfc1d886d6084113d5f3e13508f0 ·
00273fa04b9b836c553d876502e9a1e2 A
b403c6f30eec7075d0643b5d4125de1b N
00273fa04b9b836c553d876502e9a1e2 A
d3eae0ab73225a3d841241af5d8a0654
9b9233be563be442bf2edf0e3e42848d Y
4ca1a8b8e8ca22b70d69ca257d79e5ed
98c50ceddda78b850757dc37c1c0814d
4ca1a8b8e8ca22b70d69ca257d79e5ed
a952cfc1d886d6084113d5f3e13508f0 ·
Here we have ·LANGUAGE·CRYPTANALYSIS·:
a952cfc1d886d6084113d5f3e13508f0 ·
d3eae0ab73225a3d841241af5d8a0654 L
00273fa04b9b836c553d876502e9a1e2 A
b403c6f30eec7075d0643b5d4125de1b N
e3372f2164f66ea750b5b14f8166b0b9
3ea6ab81fee5f5c718f48b86e8680732 U
00273fa04b9b836c553d876502e9a1e2 A
e3372f2164f66ea750b5b14f8166b0b9
d78843699ad962a2a7c513d193d27ab4 E
a952cfc1d886d6084113d5f3e13508f0 ·
98c50ceddda78b850757dc37c1c0814d I
b403c6f30eec7075d0643b5d4125de1b N
a952cfc1d886d6084113d5f3e13508f0 ·
9e520d83ca02f81ab980ed7ff9a16526 C
ce2e2acd1155ac79105dcabcdb4fbbff R
9b9233be563be442bf2edf0e3e42848d Y
48654fae441fee7cd607d8cb90c1de44
d395fedae9dca912da1b1b50b0aca161 T
00273fa04b9b836c553d876502e9a1e2 A
b403c6f30eec7075d0643b5d4125de1b N
00273fa04b9b836c553d876502e9a1e2 A
d3eae0ab73225a3d841241af5d8a0654 L
9b9233be563be442bf2edf0e3e42848d Y
4ca1a8b8e8ca22b70d69ca257d79e5ed S
98c50ceddda78b850757dc37c1c0814d I
4ca1a8b8e8ca22b70d69ca257d79e5ed S
a952cfc1d886d6084113d5f3e13508f0 ·
This is ·CIPHERTEXT·THE·METHOD·:
a952cfc1d886d6084113d5f3e13508f0 ·
9e520d83ca02f81ab980ed7ff9a16526 C
98c50ceddda78b850757dc37c1c0814d I
48654fae441fee7cd607d8cb90c1de44 P
c98f7e77e918e98833b8fa19de4b1653 H
d78843699ad962a2a7c513d193d27ab4 E
ce2e2acd1155ac79105dcabcdb4fbbff R
d395fedae9dca912da1b1b50b0aca161 T
d78843699ad962a2a7c513d193d27ab4 E
4fdd58bb71f5f8c882eaa592d51cf647
d395fedae9dca912da1b1b50b0aca161 T
a952cfc1d886d6084113d5f3e13508f0 ·
d395fedae9dca912da1b1b50b0aca161 T
c98f7e77e918e98833b8fa19de4b1653 H
d78843699ad962a2a7c513d193d27ab4 E
a952cfc1d886d6084113d5f3e13508f0 ·
a33f02cf75488a76efb91511a0111982
d78843699ad962a2a7c513d193d27ab4 E
d395fedae9dca912da1b1b50b0aca161 T
c98f7e77e918e98833b8fa19de4b1653 H
495c118c128a67d8a0f022e3f001775e O
4065e6b94c150f4137af46b752e25204 D
a952cfc1d886d6084113d5f3e13508f0 ·
These are ·BREAKING· and ·SOLVING·:
a952cfc1d886d6084113d5f3e13508f0 ·
cb20a26ba8411b2e0072e7438ed67e54 B
ce2e2acd1155ac79105dcabcdb4fbbff R
d78843699ad962a2a7c513d193d27ab4 E
00273fa04b9b836c553d876502e9a1e2 A
3321154f7ace2161b8cafb37c6307e6b
98c50ceddda78b850757dc37c1c0814d I
b403c6f30eec7075d0643b5d4125de1b N
e3372f2164f66ea750b5b14f8166b0b9 G
a952cfc1d886d6084113d5f3e13508f0 ·
...
a952cfc1d886d6084113d5f3e13508f0 ·
4ca1a8b8e8ca22b70d69ca257d79e5ed S
495c118c128a67d8a0f022e3f001775e O
d3eae0ab73225a3d841241af5d8a0654 L
473a4eb8c699b9141c7d0bb4fa691674
98c50ceddda78b850757dc37c1c0814d I
b403c6f30eec7075d0643b5d4125de1b N
e3372f2164f66ea750b5b14f8166b0b9 G
a952cfc1d886d6084113d5f3e13508f0 ·
Here we can see ·WORLD·WAR·II·:
a952cfc1d886d6084113d5f3e13508f0 ·
b1119ba67f26c30144e9cea6a6d7059c
495c118c128a67d8a0f022e3f001775e O
ce2e2acd1155ac79105dcabcdb4fbbff R
d3eae0ab73225a3d841241af5d8a0654 L
4065e6b94c150f4137af46b752e25204 D
a952cfc1d886d6084113d5f3e13508f0 ·
b1119ba67f26c30144e9cea6a6d7059c
00273fa04b9b836c553d876502e9a1e2 A
ce2e2acd1155ac79105dcabcdb4fbbff R
a952cfc1d886d6084113d5f3e13508f0 ·
98c50ceddda78b850757dc37c1c0814d I
98c50ceddda78b850757dc37c1c0814d I
a952cfc1d886d6084113d5f3e13508f0 ·
The following stands for ·CROSSWORD·PUZZLES·IN·MAJOR·NEWSPAPERS·:
e3372f2164f66ea750b5b14f8166b0b9 G
a952cfc1d886d6084113d5f3e13508f0 ·
9e520d83ca02f81ab980ed7ff9a16526 C
ce2e2acd1155ac79105dcabcdb4fbbff R
495c118c128a67d8a0f022e3f001775e O
4ca1a8b8e8ca22b70d69ca257d79e5ed S
4ca1a8b8e8ca22b70d69ca257d79e5ed S
b1119ba67f26c30144e9cea6a6d7059c W
495c118c128a67d8a0f022e3f001775e O
ce2e2acd1155ac79105dcabcdb4fbbff R
4065e6b94c150f4137af46b752e25204 D
a952cfc1d886d6084113d5f3e13508f0 ·
48654fae441fee7cd607d8cb90c1de44 P
3ea6ab81fee5f5c718f48b86e8680732 U
ddfdaa01baab48baf54067dd3a3de527
ddfdaa01baab48baf54067dd3a3de527
d3eae0ab73225a3d841241af5d8a0654 L
d78843699ad962a2a7c513d193d27ab4 E
4ca1a8b8e8ca22b70d69ca257d79e5ed S
a952cfc1d886d6084113d5f3e13508f0 ·
98c50ceddda78b850757dc37c1c0814d I
b403c6f30eec7075d0643b5d4125de1b N
a952cfc1d886d6084113d5f3e13508f0 ·
a33f02cf75488a76efb91511a0111982 M
00273fa04b9b836c553d876502e9a1e2 A
8115f6662bacddd86db1ae8dc533c46c
495c118c128a67d8a0f022e3f001775e O
ce2e2acd1155ac79105dcabcdb4fbbff R
a952cfc1d886d6084113d5f3e13508f0 ·
b403c6f30eec7075d0643b5d4125de1b N
d78843699ad962a2a7c513d193d27ab4 E
b1119ba67f26c30144e9cea6a6d7059c W
4ca1a8b8e8ca22b70d69ca257d79e5ed S
48654fae441fee7cd607d8cb90c1de44 P
00273fa04b9b836c553d876502e9a1e2 A
48654fae441fee7cd607d8cb90c1de44 P
d78843699ad962a2a7c513d193d27ab4 E
ce2e2acd1155ac79105dcabcdb4fbbff R
4ca1a8b8e8ca22b70d69ca257d79e5ed S
a952cfc1d886d6084113d5f3e13508f0 ·
And finally, only underscores remain:
a952cfc1d886d6084113d5f3e13508f0 ·
c98f7e77e918e98833b8fa19de4b1653 H
d395fedae9dca912da1b1b50b0aca161 T
cb20a26ba8411b2e0072e7438ed67e54 B
d4dde50295a8c036709603b3c216e44d {
4ca1a8b8e8ca22b70d69ca257d79e5ed S
98c50ceddda78b850757dc37c1c0814d I
a33f02cf75488a76efb91511a0111982 M
48654fae441fee7cd607d8cb90c1de44 P
d3eae0ab73225a3d841241af5d8a0654 L
d78843699ad962a2a7c513d193d27ab4 E
97038e93767664edf41312c98285ba94
4ca1a8b8e8ca22b70d69ca257d79e5ed S
3ea6ab81fee5f5c718f48b86e8680732 U
cb20a26ba8411b2e0072e7438ed67e54 B
4ca1a8b8e8ca22b70d69ca257d79e5ed S
d395fedae9dca912da1b1b50b0aca161 T
98c50ceddda78b850757dc37c1c0814d I
d395fedae9dca912da1b1b50b0aca161 T
3ea6ab81fee5f5c718f48b86e8680732 U
d395fedae9dca912da1b1b50b0aca161 T
98c50ceddda78b850757dc37c1c0814d I
495c118c128a67d8a0f022e3f001775e O
b403c6f30eec7075d0643b5d4125de1b N
97038e93767664edf41312c98285ba94
9e520d83ca02f81ab980ed7ff9a16526 C
98c50ceddda78b850757dc37c1c0814d I
48654fae441fee7cd607d8cb90c1de44 P
c98f7e77e918e98833b8fa19de4b1653 H
d78843699ad962a2a7c513d193d27ab4 E
ce2e2acd1155ac79105dcabcdb4fbbff R
25581e56ea570e8f68c9dab82f24f36e }
a952cfc1d886d6084113d5f3e13508f0 ·
To sum up, this is the full message:
FREQUENCY ANALYSIS IS BASED ON THE FACT THAT IN ANY GIVEN STRETCH OF WRITTEN
LANGUAGE CERTAIN LETTERS AND COMBINATIONS OF LETTERS OCCUR WITH VARYING
FREQUENCIES MOREOVER THERE IS A CHARACTERISTIC DISTRIBUTION OF LETTERS THAT
IS ROUGHLY THE SAME FOR ALMOST ALL SAMPLES OF THAT LANGUAGE IN CRYPTANALYSIS
FREQUENCY ANALYSIS ALSO KNOWN AS COUNTING LETTERS IS THE STUDY OF THE
FREQUENCY OF LETTERS OR GROUPS OF LETTERS IN A CIPHERTEXT THE METHOD IS
USED AS AN AID TO BREAKING CLASSICAL CIPHERS FREQUENCY ANALYSIS REQUIRES
ONLY A BASIC UNDERSTANDING OF THE STATISTICS OF THE PLAINTEXT LANGUAGE AND
SOME PROBLEM SOLVING SKILLS AND IF PERFORMED BY HAND TOLERANCE FOR EXTENSIVE
LETTER BOOKKEEPING DURING WORLD WAR II BOTH THE BRITISH AND THE AMERICANS
RECRUITED CODEBREAKERS BY PLACING CROSSWORD PUZZLES IN MAJOR NEWSPAPERS AND
RUNNING CONTESTS FOR WHO COULD SOLVE THEM THE FASTEST SEVERAL OF THE CIPHERS
USED BY THE AXIS POWERS WERE BREAKABLE USING FREQUENCY ANALYSIS FOR EXAMPLE
SOME OF THE CONSULAR CIPHERS USED BY THE JAPANESE MECHANICAL METHODS OF
LETTER COUNTING AND STATISTICAL ANALYSIS GENERALLY HTB{SIMPLE_SUBSTITUTION_CIPHER}
CARD TYPE MACHINERY WERE FIRST USED IN WORLD WAR II POSSIBLY BY THE US ARMYS
SIS TODAY THE HARD WORK OF LETTER COUNTING AND ANALYSIS HAS BEEN REPLACED BY
COMPUTER SOFTWARE WHICH CAN CARRY OUT SUCH ANALYSIS IN SECONDS WITH MODERN
COMPUTING POWER CLASSICAL CIPHERS ARE UNLIKELY TO PROVIDE ANY REAL
PROTECTION FOR CONFIDENTIAL DATA PUZZLE PUZZLE PUZZLE
Flag
And the flag is: HTB{SIMPLE_SUBSTITUTION_CIPHER}.