Subject: [pqc-forum] OFFICIAL COMMENT: HK17
From: "D. J. Bernstein" <djb@cr.yp.to>
Reply-To: authorcontact-hk17@box.cr.yp.to
Date: 25 Dec 2017 17:15:41 -0000
To: pqc-forum@list.nist.gov
Cc: pqc-comments@nist.gov
Message-ID: <20171225171541.13354.qmail@cr.yp.to>

Dear designers, dear all,

The following attack script breaks HK17 for all proposed parameters.
Specifically, this script breaks the Python key-exchange implementation
included in the HK17 submission. This key-exchange implementation
appears to match the intent of the HK17 documentation, except that the
documentation includes a normalization step; this step does not affect
the attack.

This attack takes p+1 simple computations (and is a search so Grover's
algorithm is applicable, but all proposed parameters are small enough to
be broken by a non-quantum attack). For comparison, the submission says

   * 2^64 pre-quantum security for p=251,
   * 2^128 pre-quantum security for p=65521,
   * 2^256 pre-quantum security for p=4294967291, and
   * 2^512 pre-quantum security for p=18446744073709551557.

Our attack takes about 2^8, 2^16, 2^32, and 2^64 simple computations for
these parameter sets.

For simplicity the attack script focuses on the case that the public key
rA is invertible, which occurs almost all of the time. Slightly more
work should be able to handle the occasional exceptions.

To use this script, save the following Python code as break.py; copy
octonions.py from the HK17 submission to octonions.py in this directory;
copy HK17-O.py from the HK17 submission to ref.py in this directory; and
run "python break.py".

---Daniel J. Bernstein and Tanja Lange


import octonions
import ref
import sys

p = ref.modulo
print ref.message
print ref.times

print "eve observes public parameters and alice's public key:"
print 'oa =',ref.oa
print 'ob =',ref.ob
print 'rA =',ref.rA

def modprecip(x):
  x %= p
  if x == 0: raise Exception('dividing by 0')
  return pow(x,p-2,p)

def octonionrecip(x):
  xnormsq = sum(xi**2 for xi in x) % p
  xconj = (x[0],-x[1],-x[2],-x[3],-x[4],-x[5],-x[6],-x[7])
  return octonions.scale(xconj,modprecip(xnormsq),p)

try:
  rArecip = octonionrecip(ref.rA)
except:
  raise Exception('public key is not invertible, skipping this case for simplicity')

try:
  obrecip = octonionrecip(ref.ob)
except:
  raise Exception('ob is not invertible, should have caught from rA test')
assert octonions.multiply(obrecip,ref.ob,p) == (1,0,0,0,0,0,0,0)

# goal: write rA as x*ob*y for some x,y in \F_p[oa]
# this forces x to be in \F_p + oa\F_p
# wlog take x to be 1 or in \F_p + oa 
for i in range(p):
  for j in [0,1]:
    if j == 0 and i != 1: continue
    x0 = (i,0,0,0,0,0,0,0)
    x1 = octonions.scale(ref.oa,j,p)
    x = octonions.summ(x0,x1,p)
    try:
      xrecip = octonionrecip(x)
    except:
      continue
    t = octonions.multiply(xrecip,ref.rA,p)
    # goal: write t as ob*y for some y in \Z[oa]
    y = octonions.multiply(obrecip,t,p)
    if octonions.multiply(y,ref.oa,p) == octonions.multiply(ref.oa,y,p):
      print "eve's secret key:",x,y
      print "now eve looks at bob's ciphertext (DH public key):"
      print 'rB =',ref.rB
      k = octonions.multiply(x,octonions.multiply(ref.rB,y,p),p)
      print "eve's session key =",k
      print 'now peek at secrets to verify attack worked:'
      print "alice's session key =",ref.k1
      print "bob's session key =",ref.k2
      sys.exit(0)

-- 
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+unsubscribe@list.nist.gov.
Visit this group at https://groups.google.com/a/list.nist.gov/group/pqc-forum/.