Rating:
# Simple Logic
> Simple cipher is always strong.
This challenge gives us two files:
- `encrypt.rb`, with the algorithm used to encrypt the flag;
- `output`, with the encrypted flag and six plaintext/ciphertex pairs.
In the first file, we can see the flag and the key are randomly generated by `SecureRandom`. After encrypting the flag, another six random strings are encrypted using the same key. In the `output` file, we have six plaintext/ciphertext pairs that we can use to retrieve the key and decrypt the flag. The flag, key and plaintexts are 128 bits wide.
The encryption function adds the `msg` and `key` bits and removes an eventual 129th bit by `& mask`ing the sum; the result is XORed with `key`. This process is repeated 765 times, as defined by `ROUNDS`.
Addition can affect bits to the left: adding two 4-bit numbers can result in a 5-bit number, e.g.`1101 + 0110 = 10011`; by repeating this 765 times, up to 9 bits to the left can be affected. XOR, on the other hand, only affects the same bits.
Let's suppose `msg` ends with `0x807a`, `key` ends with `0xf254` and the encrypted `msg` ends with `0xd04a`. By adding and XORing multiple times, the last bytes of `msg` and `key` (`0x7a` and `0x54`) will affect the second to last byte of the result (`0xd0`), but the second to last bytes of `msg` and `key` (`0x20` and `0xe0`) won't affect the last byte of the result (`0x05`). This means we can guess the least significant bits of the key and, once we find them out, we can guess the next ones, until we've found the whole key.
Let's start with the info we have from `output`:
```ruby
plain = [
0x029abc13947b5373b86a1dc1d423807a,
0xeeb83b72d3336a80a853bf9c61d6f254,
0x7a0e5ffc7208f978b81475201fbeb3a0,
0xc464714f5cdce458f32608f8b5e2002e,
0xf944aaccf6779a65e8ba74795da3c41d,
0x552682756304d662fa18e624b09b2ac5
]
enc = [
"b36b6b62a7e685bd1158744662c5d04a",
"614d86b5b6653cdc8f33368c41e99254",
"292a7ff7f12b4e21db00e593246be5a0",
"64f930da37d494c634fa22a609342ffe",
"aa3825e62d053fb0eb8e7e2621dabfe7",
"f2ffdf4beb933681844c70190ecf60bf"
]
```
We will iterate the encryption key from `0x00` to `0xff`, store the encryption results into `new_enc` and compare the last byte of `enc` and `new_enc`. If the bytes are the same for the six entries simultaneously, we have a candidate for the last byte of the real key. Notice that we might have more than one valid byte, as the most significant bits might cancel out and produce a valid output. Because of this, we'll retrieve one character of the hex-encoded key at a time.
```ruby
# We know nothing about the key yet, so for now it's an empty string
known_key = ""
# We'll start comparing two characters
size = 2
# We'll save our encryption results here
new_enc = []
# Compare results go here
compare = []
# Repeat for each character of the key, except the last one
for char in 1..31
# Guess one byte at a time
for guess in 0x0..0xff
# Add our guess to what we already have
key = (guess.to_s(16) + known_key).to_i(16)
# Encrypt with the key and compare the results
for i in 0..5
new_enc[i] = encrypt(plain[i], key).to_s(16)
len1 = new_enc[i].length
len2 = enc[i].length
compare[i] = (new_enc[i][len1 - size, len1] == enc[i][len2 - size, len2])
end
# If they're all equal, we have a candidate
if compare[0] && compare[1] && compare[2] && compare[3] && compare[4] && compare[5] then
# Show the key so far
puts key.to_s(16)
# Get the new candidate
new_char = key.to_s(16)[1]
end
end
# Increase comparison size
size = size + 1
# Append the new character to what we already have
known_key = new_char + known_key
end
```
This code will produce the following output:
```
9
89
509
d09
5509
d509
3d509
bd509
73d509
f3d509
773d509
f73d509
7773d509
f773d509
67773d509
e7773d509
3e7773d509
be7773d509
53e7773d509
d3e7773d509
153e7773d509
953e7773d509
2153e7773d509
a153e7773d509
3a153e7773d509
ba153e7773d509
1ba153e7773d509
9ba153e7773d509
29ba153e7773d509
a9ba153e7773d509
7a9ba153e7773d509
fa9ba153e7773d509
57a9ba153e7773d509
d7a9ba153e7773d509
157a9ba153e7773d509
957a9ba153e7773d509
4957a9ba153e7773d509
c957a9ba153e7773d509
14957a9ba153e7773d509
94957a9ba153e7773d509
494957a9ba153e7773d509
c94957a9ba153e7773d509
4494957a9ba153e7773d509
c494957a9ba153e7773d509
5c494957a9ba153e7773d509
dc494957a9ba153e7773d509
3dc494957a9ba153e7773d509
bdc494957a9ba153e7773d509
6bdc494957a9ba153e7773d509
ebdc494957a9ba153e7773d509
2ebdc494957a9ba153e7773d509
aebdc494957a9ba153e7773d509
1aebdc494957a9ba153e7773d509
9aebdc494957a9ba153e7773d509
21aebdc494957a9ba153e7773d509
a1aebdc494957a9ba153e7773d509
521aebdc494957a9ba153e7773d509
d21aebdc494957a9ba153e7773d509
7521aebdc494957a9ba153e7773d509
f521aebdc494957a9ba153e7773d509
2f521aebdc494957a9ba153e7773d509
af521aebdc494957a9ba153e7773d509
```
Notice that for each iteration we have a pair of key parts that differ only by the most significant bit. We only find out which one is right when we compare against more bits. In the end, we have two candidates for our key: `2f521aebdc494957a9ba153e7773d509` and `af521aebdc494957a9ba153e7773d509`. Now it's easy to see which one is correct.
```ruby
#encrypted flag
enc = 0x43713622de24d04b9c05395bb753d437
candidate1 = 0x2f521aebdc494957a9ba153e7773d509
candidate2 = 0xaf521aebdc494957a9ba153e7773d509
puts decrypt(enc, candidate1).to_s(16)
puts decrypt(enc, candidate2).to_s(16)
```
Turns out both keys produce the same result, `ade4850ad48b8d21fa7dae86b842466d`, as the most significant bit is cancelled out.
Flag: `TWCTF{ade4850ad48b8d21fa7dae86b842466d}`
