[HN Gopher] An efficient key recovery attack on SIDH
       ___________________________________________________________________
        
       An efficient key recovery attack on SIDH
        
       Author : robinhouston
       Score  : 33 points
       Date   : 2022-07-30 15:06 UTC (7 hours ago)
        
 (HTM) web link (eprint.iacr.org)
 (TXT) w3m dump (eprint.iacr.org)
        
       | jnwatson wrote:
       | For background, SIKE, an implementation of SIDH, was selected as
       | a winner of the latest NIST quantum cryptography competition.
        
         | sebsebmc wrote:
         | Not exactly, it moved on to round 4 of the competition as a
         | potential backup.
        
         | est31 wrote:
         | Detail: SIKE was admitted to round 4 but was never part of the
         | selected algorithms for standardization:
         | https://csrc.nist.gov/News/2022/pqc-candidates-to-be-standar...
         | 
         | https://csrc.nist.gov/projects/post-quantum-cryptography/sel...
        
           | zinekeller wrote:
           | And I guess unless this is mitigated (this attack seems to be
           | broad enough to disqualify SIKE altogether even with heavy
           | alterations) it will not be standardised.
        
       | dhx wrote:
       | From the paper:                 "on a single core, the appended
       | Magma code breaks the Microsoft SIKE challenges $IKEp182 and
       | $IKEp217 in about 4 minutes and 6 minutes, respectively. A run on
       | the SIKEp434 parameters, previously believed to meet NIST's
       | quantum security level 1, took about 62 minutes, again on a
       | single core. We also ran the code on random instances of SIKEp503
       | (level 2), SIKEp610 (level 3) and SIKEp751 (level 5), which took
       | about 2h19m, 8h15m and 20h37m, respectively."
       | 
       | Security level 1 is meant to provide security equivalent to where
       | AES-128 is used today, security level 3 being AES-192 and
       | security level 5 being AES-256.[1]
       | 
       | If the paper is correct, it would be a brutal knockout of the
       | Microsoft team[2] from NIST PQC round 4 leaving just Kyber
       | (selected in round 3) and potentially one or more of BIKE,
       | Classic McEliece and HQC that have gone into round 4 as selected
       | PKE/KEM schemes.
       | 
       | [1] https://csrc.nist.gov/CSRC/media/Presentations/Let-s-Get-
       | Rea... (page 16)
       | 
       | [2] https://www.microsoft.com/en-us/research/project/sike/
        
         | brohee wrote:
         | It's over AFAIK, announcement here https://www.nist.gov/news-
         | events/news/2022/07/nist-announces... and CloudFlare blog here
         | https://blog.cloudflare.com/nist-post-quantum-surprise/.
         | 
         | I wonder if NIST got advance notice or if SIKE was excluded on
         | other ground, but in any case it wasn't standardized. The fact
         | SIKE went to round 4 means that NIST likely ignored the
         | attack...
        
       | est31 wrote:
       | Does this have an impact on CSIDH? I couldn't find it mentioned
       | in the paper.
        
         | zahllos wrote:
         | No but CSIDH doesn't use torsion point images because the class
         | group action is already commutative. So there's no need to
         | resolve the lack of commutativity.
         | 
         | Let me extend that comment a bit. SIDH operates over the 'full
         | endomorphism graph' which doesn't have enough structure to form
         | a class group. What we do know about it is that the ring in
         | question is isomorphic to a sub algebra that is a quaternion
         | algebra. Quaternion algebras are not commutative and this
         | property is inherited.
         | 
         | To compare to diffie hellman, imagine that when you combine
         | public material the order matters. If Alice and Bob don't find
         | a way to agree on the order the secret is computed in, they get
         | different results.
         | 
         | SIDH's torsion point images are how that agreement happens but
         | they also depend on curve parameters that relate to the secret
         | isogenies under use. It is this that is being attacked. A
         | special case was found back in 2017, but no clear way to SIDH.
         | 
         | Warning on CSIDH: like CRS before it is vulnerable to Kuperberg
         | attacks, so there's a subexpontential time attack. It's
         | arguable therefore whether it is post quantum and what
         | parameter choices are appropriate, if any.
         | 
         | This is all fine though. SIDH was never a practical contender
         | for many use cases like say smart cards, because waiting 5
         | minutes for your payment to be authorised on a 40MHz smartcard
         | processor is a bit of a no-go. SIDH is orders of magnitude
         | slower than all other options.
        
         | aildours wrote:
         | It does not seem to have a direct impact. See
         | https://nitter.it/ChrisPeikert/status/1553410345330524160#m
        
       ___________________________________________________________________
       (page generated 2022-07-30 23:02 UTC)