OFFICIAL COMMENT: HK17
Yongge Wang
Yongge Wang
D. J. Bernstein
HK17 implementation. It's easy to check this: run crypto_kem_enc() twice
and see if the results are identical. If there is in fact no secret
randomness then a break of the code is trivial.
My impression is that the intended KEM (obtained in the usual way from
the specified DH) requires the following change to the data flow in the
reference implementation: the "m", "n", and "polynomial" items obtained
from "pk" in crypto_kem_enc(), which in turn are generated randomly by
crypto_kem_keypair(), should instead be generated randomly in
crypto_kem_enc().
Of course it's the responsibility of the submitters to clearly specify
the KEM and to make sure that the reference implementation matches.
Yongge Wang writes:
> In the above proof, obviously the "commutative" property is used. As we have
> mentioned, the commutative property does not hold for quaternion (neither for
> octonion). So the correctness proof is invalid.
the stated identity follows from the Moufang identities. It's important
to note that f and h are evaluated at the same quaternion or octonion.
The submitters should spell out the details.
> f’(q_A)^m is in the format of XXX.xxxxxx...xxxx, where
> there may be 245x16x4=15680 fractional digits...
compatible with the definition of the shared secret.
The above comments should not be viewed in any way as any sort of
endorsement of the security of HK17.
---Dan
Yongge Wang
Tanja Lange and I have been discussing this, and our impression is that
the stated identity follows from the Moufang identities. It's important
to note that f and h are evaluated at the same quaternion or octonion.
The submitters should spell out the details.
> f’(q_A)^m is in the format of XXX.xxxxxx...xxxx, where
> there may be 245x16x4=15680 fractional digits...
The implementation reduces modulo (e.g.) 251 at each step, and this is
compatible with the definition of the shared secret.
D. J. Bernstein
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)
Yongge Wang
--
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/.
perret
> Le 26 déc. 2017 à 09:03, Yongge Wang <yongg...@gmail.com> a écrit :
>
> After reading Bernstein-Lange attack, one may wonder whether the scheme could be made
> secure by choosing a large enough prime p (e.g., 1000 bit p). Unfortunately, no matter how big the p it is,
> one can break the protocol by solving a homogeneous quadratic equation system of eight equations
> in four unknowns. I believe this could be done in constant steps(?) using Kipnis and Shamir’s relinearization
> techniques or the Gröbner basis algorithm or F4/F5 algorithms). For details, see
> https://webpages.uncc.edu/yonwang/octonionDH.pdf
>
> In case I am wrong, please let me know. thanks!
Do you have a code for generating these equations ?
Best Regards,
Ludovic Perret
Université Pierre et Marie Curie
Tel : 01 44 27 87 59
web : http://www-polsys.lip6.fr/~perret/
> You received this message because you are subscribed to the Google Groups "pqc-forum" group.
D. J. Bernstein
> In general, such a small system can be indeed solved very easily.
> Do you have a code for generating these equations ?
where x = x0 + x1 oa and y = y0 + y1 oa. Here oa,ob,rA are public
octonions over F_p, and x0,x1,y0,y1 are the variables in F_p.
There are really only three variables, since the equation is projective;
as the attack script says, "wlog take x to be 1 or in \F_p + oa".
---Dan
Yongge Wang
> Do you have a code for generating these equations ?
> 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/.
>
>
> --
> 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.
Peter Hecht
Dear Yongge, Dear All,
Apologise, but I must correct your comments.
1. You said "1. This submission is a Key Agreement Protocol (DH style) and seems not fall into any of the NIST PQC CFP categories (pk signature, pk encryption, kem)."
That is irrelevant. See NIST-PQC-Submission Requirements (Note pg4 "previous NIST publications have tended to describe KEMs using the term “key agreement” (also known as the key exchange), and have tended to describe public key encryption schemes using the term “key transport.”). Otherwise, as an old published fact [1], any kind of OWTF serve to construct any kind of ass[ymetric protocol (Key exchange, Key transport, ElGamalCipher, ElGamal Signature, ZKP and so on). I myself published a way to achieve that [2] using Generalized Symmetric Decomposition (GSD) as OFTW, exactly like in this PQC HK17 proposal. The fact is that you make one protocol and you easily derive the others.
[1] Baumslag G. in Designing Key Transport Protocols using Combinatorial Group Theory pp 35 in L. Gerritzen et al (Editors), Algebraic Methods in Cryptography, Contemporary Mathematics, AMS, Vol. 418, 2006
[2] “A Post-Quantum Set of Compact Asymmetric Protocols using a General Linear Group”, P. Hecht, Actas del VIII Congreso Iberoamericano de Seguridad Informática CIBSI’15, Ramió Aguirre J. el al (Eds), Universidad Politécnica de Madrid (España), 96-101 (2015) ISBN: 978-9978-301-61-6
2. You confuse non-commutativity of single arguments like quaternions or octonions with commutativity of their Polynomial powers. Two different private polynomial f(x), g(x) powers (m, n) does NOT commute if arguments (octonions o and o') are different but DO COMMUTE if arguments are the same, that means f(o)^m. g(o')^n != g(o')^n. f(o)^m but f(o)^m. g(o)^n = g(o)^n. f(o)^m. See i.e [3]. Therefore you should not be surprised that a common key is obtained at Alice and Bob sides. The arguments could be matrices and the protocol will work perfectly.
[3] Cao Z., Xiaolei D., Wang L.: New public-key cryptosystems using polynomials over non-commutative rings, Preprint arXiv/cr, eprint.iacr.org/2007/009.pdf (2007)
Thanks!
Peter
Sent from Mail for Windows 10
Peter Hecht
Dear Yongge, Dear All,
We studied your critics at https://webpages.uncc.edu/yonwang/octonionDH.pdf
and found a fatal and misleading error in it.
Your “attacked” protocol HK17-Octonions (Point 3. HK17) use simple polynomials of octonions and our proposal work (as clearly stated) with secret powers of those polynomials.
We invite you to present a correct attack or rectify your conclusions.
Yongge Wang
--
Peter Hecht
Dear Yongge, Dear All,
Thanks for your last comment.
The general idea of your critics seems to be sound, but our developer team does not give for granted how your attack would perform with a numerical example. It would not be the first time that theory differs from practical use. For that purpose, we want to see if 4. Break HK17 in O(1) steps [1] could recover with your alleged time complexity any KAT values provided by us, i.e. take our Alice/Bob values in any of this cases:
\PQC-HK17-Submission.zip\3 Optical Media\KAT\Examples with intermediate values\HK17-512bitsKeys.txt or
\PQC-HK17-Submission-updated.zip\3 Optical Media\KAT\Examples with intermediate values\HK17-256bitsKeys.txt
and obtain with your method Eve's recovered key. Your conclusions are impressive, let your arguments to be at the same level.
[1] https://webpages.uncc.edu/yonwang/octonionDH.pdf
Thanks
D. J. Bernstein
The previous attack script (Bernstein--Lange 25 Dec 2017 17:15:41 -0000)
already broke all proposed HK17 parameters. To be more precise, that
script takes at most p+1 simple computations, and the largest proposed p
was around 2^64 (with a claim of 2^512 pre-quantum security).
The new attack script is practically instantaneous even for p around
2^64. Asymptotically, the number of bit operations in the attack
algorithm is (log p)^{1+o(1)} using standard subroutines for basic
arithmetic. My impression is that the underlying computer-algebra system
already implements these subroutines. The o(1) can be reduced further.
Like the previous attack script, this script focuses on non-degenerate
cases. Experimentally, these non-degenerate cases occur almost all the
time: i.e., almost all keys are broken by the script. As before,
slightly more work should be able to handle the occasional exceptions.
To use this script, save the following Sage code as break2.sage; copy
copy HK17-O.py from the HK17 submission to ref.py in this directory; and
see the script working for p around 2^64, uncomment the line
modulo=18446744073709551557 # 64 bits
in ref.py and then run "sage break2.sage".
Internals: The previous attack script searches for octonions x,y in the
commutative ring F_p[oa] such that rA = x ob y, given oa,ob,rA. There
are p^8 octonions, but that script applies the following four speedups:
* F_p[oa] is an F_p-vector space of dimension (at most) 2. This means
that there are really just 4 variables x0,x1,y0,y1 over F_p.
* The equation rA = x ob y, a system of 8 equations over F_p, is
projective. This means that, generically, one can take x1=1, so
there are really just 3 variables x0,y0,y1 over F_p.
* The equation splits into rA / x = ob y. This allows a collision
search between 1 variable and 2 variables.
* Instead of evaluating ob y, the script checks for each x whether
(rA / x) / ob is in F_p[oa].
The new attack script starts from the same 8 equations in 3 variables
x0,y0,y1, and applies a straightforward algebraic attack, as suggested
by Wang--Malluhi and Li--Liu--Pan--Xie. Specifically, these are linear
equations in the monomials x0y0, x0y1, y0, y1; the script solves for
these monomials by linear algebra. It's conceivable that the 8 linear
equations have so many redundancies that there isn't a unique solution,
but there was always a unique solution in each of a series of several
64-bit experiments.
Presumably an analysis of the failure cases would allow a proof of the
failure probability, and, as noted above, an adaptation of the script
to handle those cases with slightly more work. But let me emphasize that
a fast high-probability attack is already a massive violation of
standard security requirements, whether or not the probability is 100%.
---Dan
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:"
oa = ref.oa; print 'oa =',oa
ob = ref.ob; print 'ob =',ob
rA = ref.rA; print 'rA =',rA
R.<t0,u0,u1> = GF(p)[]
class oct:
def __init__(self,*x):
if len(x) == 1: x = x[0]
try:
assert len(x) == 8
self.c = R(x[0]),R(x[1]),R(x[2]),R(x[3]),R(x[4]),R(x[5]),R(x[6]),R(x[7])
return
except:
self.c = R(x),R(0),R(0),R(0),R(0),R(0),R(0),R(0)
def __getitem__(self,i):
return self.c[i]
def __add__(f,g):
result = tuple(f[i] + g[i] for i in range(8))
return oct(result)
def __sub__(f,g):
result = tuple(f[i] - g[i] for i in range(8))
return oct(result)
def __mul__(x,y):
a=x[0]
b=x[1]
c=x[2]
d=x[3]
e=x[4]
f=x[5]
g=x[6]
h=x[7]
i=y[0]
j=y[1]
k=y[2]
l=y[3]
m=y[4]
n=y[5]
o=y[6]
p=y[7]
t1=(a*i-b*j-c*k-d*l-e*m-f*n-g*o-h*p)
t2=(a*j+b*i+c*m+d*p-e*k+f*o-g*n-h*l)
t3=(a*k-b*m+c*i+d*n+e*j-f*l+g*p-h*o)
t4=(a*l-b*p-c*n+d*i+e*o+f*k-g*m+h*j)
t5=(a*m+b*k-c*j-d*o+e*i+f*p+g*l-h*n)
t6=(a*n-b*o+c*l-d*k-e*p+f*i+g*j+h*m)
t7=(a*o+b*n-c*p+d*m-e*l-f*j+g*i+h*k)
t8=(a*p+b*l+c*o-d*j+e*n-f*m-g*k+h*i)
return oct(t1,t2,t3,t4,t5,t6,t7,t8)
def __repr__(self):
return '(%s)' % ', '.join('%s' % x.change_ring(ZZ) for x in self)
t = oct(t0) + oct(oa)
u = oct(u0) + oct(u1) * oct(oa)
v = t * oct(ob) * u - oct(rA)
M = matrix(GF(p),8,5)
for i in range(8):
w = v[i]
M[i,0] = w[0,0,0]
M[i,1] = w[0,0,1]
M[i,2] = w[0,1,0]
M[i,3] = w[1,0,1]
M[i,4] = w[1,1,0]
assert w == M[i,4]*t0*u0+M[i,3]*t0*u1+M[i,2]*u0+M[i,1]*u1+M[i,0]
K = M.right_kernel()
if K.dimension() != 1:
raise Exception('kernel dimension is not 1, skipping this case for simplicity')
B = K.basis()[0]
if B[0] != 1:
raise Exception('kernel does not involve constant, skipping this case for simplicity')
x0y0 = B[4]
x0y1 = B[3]
y0 = B[2]
y1 = B[1]
if y0:
x0 = x0y0/y0
elif y1:
x0 = x0y1/y1
else:
x0 = 0 # key must be 0; probably forces bigger basis anyway
x = oct(list(ti(x0,y0,y1) for ti in t))
y = oct(list(ui(x0,y0,y1) for ui in u))
print "eve's secret key =",x,y
print '-----'
print "now eve looks at bob's ciphertext (DH public key):"
print 'rB =',ref.rB
print 'we now peek at secrets to verify attack worked:'
Alperin-Sheriff, Jacob (Fed)
All:
This also didn’t get posted to the forum because it had an attachment (the attachment appears to be identical to this eprint particle by Yanbin Pan et al https://eprint.iacr.org/2017/1259.pdf)
We will try to figure something out about hosting attack code; in the mean time, if possible, please upload it elsewhere and link to it in OFFICIAL COMMENT emails rather than attaching it because in the latter case nobody will see it.
From: Yanbin Pan <pany...@amss.ac.cn>
Date: Wednesday, December 27, 2017 at 5:32 AM
To: pqc-comments <pqc-co...@nist.gov>
Cc: pqc-forum <pqc-...@list.nist.gov>
Subject: OFFICIAL COMMENT: HK17
Dear Dr. Chen, Moody, and Liu,
We group find that the key exchange scheme HK17 is not secure. Any passive adversary can recover the shared key very efficiently.
The key observation is that any octonion (or quaternion) satisfies a quadratic equation, so for any octonion o_A, and any polynomial g(x), we can find a,b such that g(o_A)= a o_A+b.
For HK17, since r_A=f(o_A)^m o_B f(o_A)^n, we can write r_A=(a o_A+b)o_B (c o_A+d) where a,b,c,d are unknowns. By solving a system of linear equations over Z_p, we can find a solution a, b, c d.
Next we can prove that (a o_A+b)r_B (c o_A+d) equals the shared key.
See the attachment for more details.
Best regards,
Yanbin
Peter Hecht
Dear Dan and Tanja, dear all,
Thanks to all for helpful comments.
Despite some pointless objections received, we are convinced that your original idea works as pretended (see Bernstein & Lange, Dec 25.). Later Li et al only confirmed that, but the credit is clearly yours. As a logical consequence, we withdraw our proposal because our modifications are far beyond allowed changes for the first round. We have in mind to block linearizing attacks switching from Moufang loop to GF(2^8) operations, were octonions work now as field members.
More details over our HK17plus protocol could be downloaded (and hopefully commented) at https://1drv.ms/b/s!ArmCj8o3U1Iyuzd5X8bE9v5sdz57
Best wishes!
Peter