Two parties, Alice and Bob, want to exchange a message in secret, even if they are watched by an attacker. They start with a collection of points. The elliptic curve is represented by points. Draw an edge between the two points if you can turn one curve into another. If you walk along the edges of the graph, you will end up in a random place.
The edges of Bob and Alice's graphs are different because of their different isogenies. Alice and Bob keep a record of their path from one point to another by hopping along random edges on their own graph. Each publishes their end location but hides their path.
Alice goes to Bob's last point, and Bob goes to Alice's first point. They repeat their secret walk. Both of them will end up at the same point.
The secret location has been found so that Alice and Bob can use it as their secret key. If an attacker sees the intermediate points that Alice and Bob send each other, they don't know Alice's or Bob's secret walk, so they can't figure it out
Alice and Bob need to give each other more information about their walks. SIDH fell because of extra information.
Thomas Decru didn't plan on breaking SIDH. He was trying to generalize the method to make it better. His approach may be useful for attacking SIDH. He approached Wouter Castryck, his colleague at the Catholic University of Leuven in Belgium and one of his former advisers, and they dove into the literature.
The paper was published in 1997. It was almost immediately applicable to SIDH. The attack came in a couple of days.
It felt special. One of our favorites was killed by us.
Wouter Castryck is a professor at the University of Leuven.
To recover Alice's secret walk, Castryck and Decru examined the product of two elliptic curves. An abelian surface is a type of surface. The abelian surfaces, Kani's theorem, and the extra information Alice gave Bob were used to find each step.
Jao said it was almost like a homing signal that let you lock in. The signal tells you that you should go to the next step. They were able to get to Alice and Bob.
Jao said it was a very unexpected approach, going to more complicated objects to get results.
"I was very excited to see this technique being used, I have worked on abelian surfaces and helped develop isogeny-based cryptography." Shame on me because I didn't think about breaking it as a way to do it.
The lowest-security version of the SIDH protocol was broken by Castryck and Decru in less than an hour. It took just 10 minutes to break the low-security version and a couple hours to break the high-security version. SIDH can't be salvaged because of more general attacks in the past few weeks.
Castryck said it was a special feeling but also a sad one. One of our favorites was killed by us.
It's not possible to guarantee that a system is safe. Cryptographers rely on a lot of time passing and a lot of people trying to break the problem. Jeffrey Hoffstein is a mathematician at Brown University.
Competitions like NIST are crucial. The previous round of the NIST competition, Ward Beullens created an attack that broke a scheme called Rainbow. He was able to stage his attack after he saw the underlying mathematical problem from a different perspective. The system that was broken relied on different mathematics than most proposed post-quantum protocols.
The recent attacks were a big deal according to Thomas Prest. They show how hard it is to study the security of various systems. He said that a mathematical object could have an exploitable structure in one perspective and no obvious structure in the other. Identifying the right new perspective is difficult.
All Rights Reserved © 2024
