Neoquest 2018: “Airship? Yeah! ”

CTF NeoQuest 2018 has recently ended. Under the cat analysis of the second part of the task about the airship, ZeroNet , the shift register with feedback and the system of linear equations.

The task was given the address of the site on the ZeroNet network, where the chat is deployed. Since in ZeroNet, the contents of the site are downloaded to the local computer, then having stuck the folder with the site, I found the first key, as well as encrypted_storage.json:

{ "encrypted_storage": [ { "secret_name": "SiteName", "secret_value": "84a303b9f188b0", "date_added": 1519915207692 }, { "secret_name": "SiteAddress", "secret_value": "e68cd4a46ee074121a040a6188d3f6d495f24480fc0e08b0d45d8fba875d9fd38e88", "date_added": 1519915235730 }, { "secret_name": "AdminUsername", "secret_value": "0d9ef480aa", "date_added": 1519915256867 }, { "secret_name": "AdminCert", "secret_value": "4b95e6dfd893b37293fe041188cd6d8da5af08d4fb80b0", "date_added": 1519915282130 }, { "secret_name": "SecondKey", "secret_value": "c73ab54b91c6099b0f0081ea9124e2f50e846f6fc674046b3b41a86048ae3e27b04d354c9b9786a158f9722821005362bcfae8d6c0a261addb0b2ef8e16fbdfc851b82e0829d", "date_added": 1519915320471 } ] } 

Apparently, we need to decrypt “secret_value”. You may notice that the length of the ciphertext for AdminUsername is 5 bytes. Perhaps clear text - “admin”? If it is a gamma cipher, then we can get 5 bytes of gamma and check whether they are suitable for other "secrets". Check on the first 5 bytes of SiteName , we get b "\ xe8Y \ x9aP5". The result is not very ...

Another site has this page:
')


Stumbling, you can see that the length of the ciphertext is equal to the length of the plaintext, and encryption and decryption is the same operation. Very similar to gamma, maybe there is the same algorithm that is encrypted second secret?

The algorithm itself is in the js / lfsr.js file . Gamma in it is generated by function

  function genKeyStream(key, iv, length) { var res = [] var state_len = bitLength(key) var state = iv.mod(bigInt(1).shiftLeft(state_len)) for (var i = 0; i < length; i++) { var next_byte = 0 for (var j = 0; j < 8; j++) { var next_bit = bitCount(state.and(key)) % 2 next_byte = (next_byte >>> 1) | (next_bit << 7) state = state.shiftRight(1).or(bigInt(next_bit).shiftLeft(state_len - 1)) } res.push(next_byte) } return res.reverse() } 

This is a shift register with feedback. The register length is equal to the key length; the location of the taps is specified by the key. IV is cut to the length of the key and is used as the initial fill. Only in contrast to the usual shift register with feedback, here the gamma is taken not from the output of the register, but from its input.

You can also see that the first bytes of the gamma will encrypt the last bytes of the OT ... We return to encrypted_storage.json , take the gamma from “admin” and shuffle the last 5 bytes of SiteName to it : “oChat” is a completely different result! We decipher the end of the SiteAddress line - we see that the line contains “1NeoChatZK4DxZJdg5WwocwxcUppA1eJgL” - the site address. The length of this string is 34 bytes, i.e. we have the first 34 bytes (272 bits) gamma.
In principle, encryption using shift registers is no longer considered persistent, but still having only a small piece of the gamut won't easily break it ... But this cipher has a slight difference from the “classics” - the gamma is taken from the register input. After thinking about it, it can be understood that after L = len (key) iterations IV will be completely “forced out” of the shift register, and the entire internal state (register filling) will be equal to the last L bits of the gamma. Then for all $$$i \ geq L$You can write the following equation:

$$

$$G_ {i-1} * K_ {L-1} + G_ {i-2} * K_ {L-2} + ... + G_ {i-L} * K_ {0} = G_i$$

Where:
$$$G_i$- i-th bit of gamma
$$$K_i$- i-th key bit
$$$L$- key length
$$$*$- logical AND
$$$+$- exclusive OR (XOR)
Solving a system of L such equations, one can find the key. And knowing the key and the internal state (the last L bits of the gamma), you can generate as many gammas as you need! In order for a system to have at most one solution, it must have at least L linearly independent equations. Those. on the right side will stand $$$G_i$for $$$i \ in [L, 2L - 1]$. So we can solve the problem if the key length is not more than $$$272/2 = $ 13$bit.

To solve it, I had to write a function that solves the system according to the Gauss method, since all the ready-made functions found solved everything in the field of real or complex numbers, and not on the set (0, 1) with the AND and XOR operations. Then I went through different values ​​of L, if the system turned out to be joint, I checked whether the next bits of the gamma generated by such a key would match those known to me. Match for $$$L = 128$. A few minutes later the key was counted!

In fact, it was possible not to go through different Ls, but to immediately write down a system of 134 equations with 134 unknowns, just for the key, the first 6 bits would be zero.