Nokta_strigo March 21, 2018 at 00:50

Neoquest 2018: “Airship? Aha! ”

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

In the task, the address of the site on the ZeroNet network was given , on which the chat was deployed. Because in ZeroNet, the contents of the site are downloaded to the local computer, then, scrubbing 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 ciphertext length for AdminUsername is 5 bytes. Perhaps the plaintext is “admin”? If this is a gamma cipher, then we can get 5 bytes of gamma and check if they fit other "secrets". We check on the first 5 bytes of SiteName , we get b "\ xe8Y \ x9aP5". The result is not very ...

Also on the site there is such a page:

Having stumbled, you can see that the length of the ciphertext is equal to the length of the plaintext, and encryption and decryption are one and the same operation. It is very similar to gamming, maybe the same algorithm is used to encrypt the second secret?

The algorithm itself is located in the js / lfsr.js file . The gamma in it is generated by the 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 feedback shift register. The length of the register is equal to the length of the key, the location of the taps is set 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 feedback shift register, here the gamma is taken not from the output of the register, but from its input.

It can also be seen that the first bytes of the gamma will encrypt the last bytes FROM ... We return to encrypted_storage.json , take the gamma from “admin” and decrypt the last 5 bytes of SiteName : “oChat” is a completely different result! We decipher the end of the line SiteAddress- we see that in the line “1NeoChatZK4DxZJdg5WwocwxcUppA1eJgL” is written - the address of the site. The length of this string is 34 bytes, i.e. we have the first 34 bytes (272 bits) of the gamut.
In principle, encryption using shift registers has not been considered strong for a long time, but still having only a small piece of the gamma can’t just break it ... But this cipher has a slight difference from the “classic” - the gamma is taken from the register input. Thinking about this, we can understand that after L = len (key) iterations IV will be completely “squeezed out” from the shift register, and the entire internal state (register filling) will be equal to the last L bits of the gamma. Then for everyone

$i \ geq L$ you can write this equation:

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

Where:

$inline$ - i-th gamma bit

$inline$ - i-th key bit

$inline$ - key length

$inline$ - logical AND

$inline$ - exceptional OR (XOR)
Having solved a system of L such equations, you can find the key. And knowing the key and the internal state (the last L bits of the gamma), you can generate as much gamma as you need! 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

$inline$ for

$i \ in [L, 2L - 1]$ . So we can solve the problem if the key length is not more than

$inline$ bit.

To solve it, I had to write a function that solves the system according to the Gauss method, because all found ready-made functions solved everything in the field of real or complex numbers, and not on the set (0, 1) with AND and XOR operations. Then I went over different values of L, if the system turned out to be joint, I checked whether the next gamma bits generated by such a key would match the ones I knew. There was a match for

$inline$ . After a couple of minutes, the key was counted!

In fact, it was possible not to sort 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.

Decision code

from hashlib import sha1
N_ct = 70 * 8
N = 0x22 * 8
O_hex = "D7 C2 B1 CB 2D 88 15 66 40 4F 3E 25 F0 89 BC B0 F2 C7 13 F7 93 6D 7F C8 B7 08 FF CA C6 6C FA 99 E9 C4".replace(" ", "")
O_int = int(O_hex, 16)
O = [int(c) for c in bin(O_int)[2:]]
O.reverse()
O_full = O_int
ct = int("C7 3A B5 4B 91 C6 09 9B 0F 00 81 EA 91 24 E2 F5 0E 84 6F 6F C6 74 04 6B 3B 41 A8 60 48 AE 3E 27 B0 4D 35 4C 9B 97 86 A1 58 F9 72 28 21 00 53 62 BC FA E8 D6 C0 A2 61 AD DB 0B 2E F8 E1 6F BD FC 85 1B 82 E0 82 9D".replace(" ", ""), 16)
def solve_linear_eq(A):
    """A[l, l+1]"""
    l = len(A)
    assert len(A) + 1 == len(A[0])
    for j in range(l):
        for i in range(j, l):
            if A[i][j] == 1:
                break
        A[j], A[i] = A[i], A[j]
        for i in range(l):
            if i != j and A[i][j] == 1:
                for k in range(l + 1):
                    A[i][k] ^= A[j][k]
    for i in range(l):
        for j in range(l):
            if i != j and A[i][j] == 1 or i==j and A[i][j] == 0:
                return None
    return [A[i][-1] for i in range(l)]
def preapare_linear_eq(L):
    A = []
    for n in range(L, 2*L):
        A.append([])
        for i in range(0, L):
            A[-1].append(O[n-L+i])
        A[-1].append(O[n])
    return A
def gamma(K):
    O_full = O.copy()
    L = len(K)
    for n in range(N, N_ct):
        s = 0
        for i in range(0, L):
            s ^= O_full[n - L + i] & K[i]
        O_full.append(s)
    return O_full
def check_key(K):
    for n in range(L, N):
        s = 0
        for i in range(0, L):
            s ^= O[n - L + i] & K[i]
        if s != O[n]:
            return False
    return True
found = 0
not_found = 0
for L in range(8, N//2):
    A = preapare_linear_eq(L)
    K = solve_linear_eq(A)
    if K is not None and check_key(K):
        found += 1
        print(L, K)
        O_full = gamma(K)
        O_full_int = 0
        O_full.reverse()
        for O in O_full:
            O_full_int = (O_full_int << 1) + O
        pt = O_full_int ^ ct
        pt = pt.to_bytes(70, "big")
        print(pt)
        break
    else:
        not_found += 1
print(sha1(pt).hexdigest())

Tags:

Neoquest 2018: “Airship? Aha! ”

Also popular now: