still not rsa

Same-ish problem as in so easy but not rsa but now it’s time to deal with the actual cryptosystem. See that task for code, though the parameter is smaller, and now the goal is to decrypt a ciphertext where the AES key is the secret polynomial.

Unfortunately it also had a ton of problems and was updated like three times. It seemed unsolvable when I first looked at it (you didn’t even get the IV for the AES cipher), so I left it for last.

Like I mentioned in that task I didn’t really know it was NTRU, and I spent several hours figuring out the basics of how the system worked on my own. It was the last problem and I didn’t really have anything to do after, I had all the time in the world, so this was just me playing around, and I’m usually not a fan of Googling. I found you could overflow the “outer” when decrypting, and the resulting polynomial gave really short polynomials when multiplied with the secret key. Cue a lot of pen&paper-work and I figured this is related to monomials that the public key (or really its g component) shared with the secret key, and it happens when the coefficient goes outside the range when two such monomials are summed, but stays within it when this doesn’t happen.

Although short, these polynomials were still too long to brute force. (10-20 terms?) At this point I also tried several lattice approaches. Large lattices seemed untenable, although with “narrow” lattices I had some success in recovering parts of g if I could guess some of the zeroed out coefficient. It seemed very error prone and didn’t feel confident it would work efficiently for the full key. So this problem took up most of my time and I probably spent a full day on it due to this stubbornness.

Finally I did end up Googling, and that’s when I wound it was NTRU, and I learned various attacks, such as the one I sort of stumbled into above, but worked out to a much more sophisticated degree. I.e. you can provide a polynomial like for decryption and they will all give short polynomials, and it seems the more you layer this the smaller the overlap area — will likewise have to be adjusted so we’re only “targetting” an area where more monomials overlap — so you end up getting back very short polynomials indeed — monomials or binomials. For this you can work in and try dividing mono- or binomials by the polynomial in a brute force fashion and sometimes (rather often) the secret key pops out.

This is what I did.


n, q = 167, 128

R, iv, flag_enc, pk = connect()
h = bq(pk*43)

Zx.<x> = ZZ[]
Zq.<z> = Zmod(q)[]
Z3.<t> = Zmod(3)[]
ZR.<r> = Z3.quotient(t^n - 1)
poly_targets = [ZR(sum(x^i for i in es)) for es in combos(range(n), [1,2])]

C = convolution
bq = lambda s: balancedmod(C(s,1),q)
b3 = lambda s: balancedmod(C(s,1),3)

def test(k, send):
  ct = decode( 24*(h*x^k + h + 1) )
  m = send(ct)
  zm = ZR(m)

  if not zm.is_unit():
    print(k, 'skipping non-unit')
    return None

  zm = 1/zm
  for p in poly_targets:
    _f = test_secret(p*zm)
    if _f is not None:
      return _f

def test_secret(ss):
  cc = Counter(ss)
  if cc[1] == 60 and cc[2] == 61:
    ss = -ss
  elif cc[1] != 61 or cc[2] != 60:
    return None
  f = b3(Zx(ss.lift()))
  cc = Counter( balancedmod(C(pk, f), q) )
  if cc[3] != 15 or cc[-3] != 15:
    print("rejected candidate!", cc)
    return None
  return f


for k in range(2, n):
  print(k, "new round")
  if (_sk := test(k,lambda ss: exchange(R,ss))) is not None:
    print(k, "secret key found: ", _sk)
    break