search

aszepieniec / falcon-rust

A rust implementation of the Falcon post-quantum signature scheme
MIT License
8 stars 2 forks source link

Possible infinite loop in `babai_reduce`. #3

Open aszepieniec opened 8 months ago

aszepieniec commented 8 months ago

For certain inputs the the loop in babai_reduce in falcon.rs does not terminate. Unfortunately, it is difficult to trigger this behavior -- or I don't know how. Best I can do is catch the inputs when it happens, which is now done with a loop counter and a panic if the counter exceeds an arbitrary threshold.

aszepieniec commented 6 months ago

With a framework like proptest, if the behavior is observed, it will be deterministically reproducible and moreover reduced to a minimally complex instance that still fails.

aszepieniec commented 6 months ago

The Falcon team, in consultation with NIST, has decided to modify the keygen algorithm, see #7 . As a result of this modification, this issue may be solved.