Hey Jeffrey, I've posted an answer on SE, but will give a short summary of what I think solves the problem here. Please contact the author to make sure my proposed fix solves the problem.
Now the summary: The added checks at the end of the loop finding the blinding value r should ensure that r is always a square modulo n (and hence also modulo p and q). The checks were split because if both checks would output "-1" the "faster" check using Jacobi(r,n) would have output "1" meaning it's a "square". So as we need a square I proposed that after we generated the r, we square it (mod n) and then it should always pass the two tests by definition, meaning the checks can be dropped and the loop only needs to iterate once if q!=r!=p, which is very likely as the probability that r is either p or q should be around 2^-1000. As a "bonus", if it's later needed to find the square root of r, the pre-squaring value can be stored and later used for this purpose. I think that will solve our problem concerning the blinding value. BR JPM Am 14.06.2015 um 06:04 schrieb Jeffrey Walton: > Hi Everyone, > > Attached is a proposed patch for CVE-2015-2141 mitigation, blinding > and OpenMP support. Information can be found at Evgeny Sidorov's > "Breaking the Rabin-Williams digital signature system...", > https://eprint.iacr.org/2015/368. > > The goals of the patch were to: > > (1) mitigate CVE-2015-2141 > (2) improve CalculateInverse efficiency > > There are two mitigations available for (1). First is to disable > blinding (A). Second is to ensure the blinding value satisfies > preconditions (B). Both are available in the patch. By default, > blinding is enabled, so exiting behavior is preserved. > > For (2), Bernstein's Tweaked Roots was provided with precomputation. > Its controlled by CRYPTOPP_USE_RW_TWEAKED_ROOTS in config.h. It is > enabled by default. > > More details are below and in the patch. > > Any feedback or comments are welcomed. > > ***** > > For (1)(A), an alternate constructor is provided. > > void Initialize(const Integer &n, const Integer &p, const Integer &q, > const Integer &u, bool blinding = true); > > And: > > bool GetEnableBlinding() const {return m_blinding;} > void SetEnableBlinding(bool enabled) {m_blinding = enabled;} > > valida2.cpp was modified to test both cases (enabled/disabled). > > ***** > > The constructor was used because IsolatedInitialize was not available. > The following failed to compile: > > signer.IsolatedInitialize(g_nullNameValuePairs); > signer.AccessKey().IsolatedInitialize(g_nullNameValuePairs); > > In general, IsolatedInitialize is available on Filters, so its not > surprising. > > ***** > > For (1)(B), Sidorov's fix was applied: > > do { > r.Randomize(rng, Integer::One(), m_n - Integer::One(), > Integer::ANY); > rInv = modn.MultiplicativeInverse(r); > } while (rInv.IsZero() || (Jacobi(r % m_p, m_p) == -1) || > (Jacobi(r % m_q, m_q) == -1)); > > The actual fix was a little more involved because of running times and > OpenMP. > > Jacobi runs in O(m*log(n)), and Modular Inversion runs in O(n^2). > Jacobi runs faster than the modular inversion, so Jacobi was tested > first. If the Jacobi's succeed, then we move on to the inversion. > > ***** > > I *think* there's a better way to calculate the blinding value, but I > don't know what it is. Under trial and error, we're executing the loop > as little as 1 time and as many as 10 or 12 times (average about 6-8). > > I've experimented with random values with different forms and > equivalence classes, and I get get worse case down to about 3. But I > need to understand it better before I go further with it. There's an > open question here: > https://crypto.stackexchange.com/questions/26226/blinding-value-of-particular-form. > > ***** > > For (2), both the existing and new implementations are available. > > Its controlled by CRYPTOPP_USE_RW_TWEAKED_ROOTS in config.h. It is > enabled by default. > > ***** > > Tweaked Roots can take advantage of precomputation, but existing > callers {do|did} *not* call signer.Precompute(). So the precomutation > is performed lazily in CalculateInverse: > > if(!m_precompute) > Precompute(0 /*unused*/); > > CalculateInverse is a const function, and the desire to avoid > behavioral changes for callers meant we had to do this because: > > #ifdef CRYPTOPP_USE_RW_TWEAKED_ROOTS > bool SupportsPrecomputation() const {return true;} > void Precompute(unsigned int); > void Precompute(unsigned int) const {return > const_cast<ThisClass*>(this)->Precompute(0);} > #endif > > We felt is was safer to have a non-const Precompute() perform the > operation, and const-cast away the const-ness. This is because (1) > existing classes do it that way, and (2) the compiler will be less > likely to optimize away things that are being assigned. > > ***** > > Our other const-ness option is to make m_pre_2_9p, m_pre_2_3q, > m_pre_q_p and m_precompute mutable. That potentially lead to duplicate > code. > > ***** > > diff --git a/config.h b/config.h > index 77c34b9..602fd82 100644 > --- a/config.h > +++ b/config.h > @@ -46,6 +46,9 @@ > // set the name of Rijndael cipher, was "Rijndael" before version 5.3 > #define CRYPTOPP_RIJNDAEL_NAME "AES" > > +// define this to use Tweaked Roots as detailed by Bernstein in > http://cr.yp.to/sigs/rwsota-20080131.pdf. > +#define CRYPTOPP_USE_RW_TWEAKED_ROOTS > + > // ***************** Important Settings Again ******************** > // But the defaults should be ok. > > diff --git a/rw.cpp b/rw.cpp > index cdd9f2d..8c4ac8f 100644 > --- a/rw.cpp > +++ b/rw.cpp > @@ -5,6 +5,10 @@ > #include "nbtheory.h" > #include "asn.h" > > +#ifndef NDEBUG > +# include <cassert> > +#endif > + > #ifndef CRYPTOPP_IMPORTS > > NAMESPACE_BEGIN(CryptoPP) > @@ -99,8 +103,69 @@ void > InvertibleRWFunction::GenerateRandom(RandomNumberGenerator &rng, const > Name > > m_n = m_p * m_q; > m_u = m_q.InverseMod(m_p); > + > +#ifdef CRYPTOPP_USE_RW_TWEAKED_ROOTS > + Precompute(0 /*unused*/); > +#endif > } > > +void > InvertibleRWFunction::GenerateBlindingValue(RandomNumberGenerator& > rng, Integer& r, Integer& rInv) const > +{ > + ModularArithmetic modn(m_n); > + bool stop = false; > + > + while(!stop) > + { > + // Jacobi is O(m*log(n)); ModInv is O(n^2). Perform the > Jacobi's first > + r.Randomize(rng, Integer::One(), m_n - Integer::One()); > + > + int jp, jq; > + #pragma omp parallel sections > + { > + #pragma omp section > + jp = Jacobi(r % m_p, m_p); > + #pragma omp section > + jq = Jacobi(r % m_q, m_q); > + } > + > + if ((jp != -1) && (jq != -1)) > + { > + rInv = modn.MultiplicativeInverse(r); > + if(rInv.NotZero()) > + stop = true; > + } > + } > +} > + > +void InvertibleRWFunction::Initialize(const Integer &n, const Integer > &p, const Integer &q, const Integer &u, bool blinding) > +{ > + m_n = n; m_p = p; m_q = q; m_u = u; > + m_blinding = blinding; > + > +#ifdef CRYPTOPP_USE_RW_TWEAKED_ROOTS > + Precompute(0 /*unused*/); > +#endif > +} > + > +#ifdef CRYPTOPP_USE_RW_TWEAKED_ROOTS > +void InvertibleRWFunction::Precompute(unsigned int /*unused*/) > +{ > + ModularArithmetic modp(m_p), modq(m_q); > + > + #pragma omp parallel sections > + { > + #pragma omp section > + m_pre_2_9p = modp.Exponentiate(2, (9 * m_p - 11)/8); > + #pragma omp section > + m_pre_2_3q = modq.Exponentiate(2, (3 * m_q - 5)/8); > + #pragma omp section > + m_pre_q_p = modp.Exponentiate(m_q, m_p - 2); > + } > + > + m_precompute = true; > +} > +#endif > + > void InvertibleRWFunction::BERDecode(BufferedTransformation &bt) > { > BERSequenceDecoder seq(bt); > @@ -109,6 +174,10 @@ void > InvertibleRWFunction::BERDecode(BufferedTransformation &bt) > m_q.BERDecode(seq); > m_u.BERDecode(seq); > seq.MessageEnd(); > + > +#ifdef CRYPTOPP_USE_RW_TWEAKED_ROOTS > + m_precompute = false; > +#endif > } > > void InvertibleRWFunction::DEREncode(BufferedTransformation &bt) const > @@ -121,17 +190,96 @@ void > InvertibleRWFunction::DEREncode(BufferedTransformation &bt) const > seq.MessageEnd(); > } > > +#ifdef CRYPTOPP_USE_RW_TWEAKED_ROOTS > +// DJB's "RSA signatures and Rabin-Williams signatures..." > (http://cr.yp.to/sigs/rwsota-20080131.pdf). > +Integer InvertibleRWFunction::CalculateInverse(RandomNumberGenerator > &rng, const Integer &x) const > +{ > + // Enforces p in {3 + 8Z} and q in {7 + 8Z}. Tweaked roots will > always be available. > + DoQuickSanityCheck(); > + > + if(!m_precompute) > + Precompute(0 /*unused*/); > + > + ModularArithmetic modn(m_n), modp(m_p), modq(m_q); > + Integer r, re, rInv; > + > + // Modified due to Sidorov, CVE-2015-2141 and "Breaking the > Rabin-Williams digital signature system..." > (https://eprint.iacr.org/2015/368). > + if(m_blinding) > + { > + GenerateBlindingValue(rng, r, rInv); > + re = modn.Square(r); > + re = modn.Multiply(re, x); // blind > + } > + > + const Integer &h = (m_blinding ? re : x), &p = m_p, &q = m_q, &n > = m_n; > + Integer e, f; > + > + const Integer U = modq.Exponentiate(h, (q+1)/8); > + if(((modq.Exponentiate(U, 4) - h) % q).IsZero()) > + { > + e = Integer::One(); > + } else { > + e = -1; > + } > + > + const Integer eh = e*h; > + > + const Integer V = modp.Exponentiate(eh, (p-3)/8); > + if(((modp.Multiply(modp.Exponentiate(V, 4), modp.Exponentiate(eh, > 2)) - eh) % p).IsZero()) > + { > + f = Integer::One(); > + } else { > + f = 2; > + } > + > + Integer W, X; > + #pragma omp parallel sections > + { > + #pragma omp section > + { > + W = (f.IsUnit() ? U : modq.Multiply(m_pre_2_3q, U)); > + } > + > + #pragma omp section > + { > + const Integer t = modp.Multiply(modp.Exponentiate(V, 3), eh); > + X = (f.IsUnit() ? t : modp.Multiply(m_pre_2_9p, t)); > + } > + } > + > + const Integer Y = W + q * modp.Multiply(m_pre_q_p, (X - W)); > + > + // Signature > + Integer s = (m_blinding ? modn.Multiply(modn.Square(Y), rInv) : > modn.Square(Y)); > + > + // Bernstein states this should always be the case. > + assert((e * f * s.Squared()) % m_n == x); > + > + // IEEE P1363, 8.2.8 IFSP-RW, p.44 > + s = STDMIN(s, m_n - s); > + if (ApplyFunction(s) != x) // check > + throw Exception(Exception::OTHER_ERROR, > "InvertibleRWFunction: computational error during private key operation"); > + > + return s; > +} > +#else // Existing implmentation > Integer InvertibleRWFunction::CalculateInverse(RandomNumberGenerator > &rng, const Integer &x) const > { > DoQuickSanityCheck(); > ModularArithmetic modn(m_n); > - Integer r, rInv; > - do { // do this in a loop for people using small numbers for > testing > - r.Randomize(rng, Integer::One(), m_n - Integer::One()); > - rInv = modn.MultiplicativeInverse(r); > - } while (rInv.IsZero()); > - Integer re = modn.Square(r); > - re = modn.Multiply(re, x); // blind > + Integer r, rInv, re; > + > + // Modified due to Sidorov, CVE-2015-2141 and "Breaking the > Rabin-Williams digital signature system..." > (https://eprint.iacr.org/2015/368). > + if(m_blinding) > + { > + GenerateBlindingValue(rng, r, rInv); > + re = modn.Square(r); > + re = modn.Multiply(re, x); // blind > + } > + else > + { > + re = x; > + } > > Integer cp=re%m_p, cq=re%m_q; > if (Jacobi(cp, m_p) * Jacobi(cq, m_q) != 1) > @@ -140,22 +288,25 @@ Integer > InvertibleRWFunction::CalculateInverse(RandomNumberGenerator &rng, const > cq = cq.IsOdd() ? (cq+m_q) >> 1 : cq >> 1; > } > > - #pragma omp parallel > - #pragma omp sections > - { > - #pragma omp section > - cp = ModularSquareRoot(cp, m_p); > - #pragma omp section > - cq = ModularSquareRoot(cq, m_q); > - } > + #pragma omp parallel sections > + { > + #pragma omp section > + cp = ModularSquareRoot(cp, m_p); > + #pragma omp section > + cq = ModularSquareRoot(cq, m_q); > + } > > Integer y = CRT(cq, m_q, cp, m_p, m_u); > - y = modn.Multiply(y, rInv); // unblind > + > + if(m_blinding) > + y = modn.Multiply(y, rInv); // unblind > + > y = STDMIN(y, m_n-y); > if (ApplyFunction(y) != x) // check > throw Exception(Exception::OTHER_ERROR, > "InvertibleRWFunction: computational error during private key operation"); > return y; > } > +#endif // CRYPTOPP_USE_RW_TWEAKED_ROOTS > > bool InvertibleRWFunction::Validate(RandomNumberGenerator &rng, > unsigned int level) const > { > @@ -189,6 +340,10 @@ void InvertibleRWFunction::AssignFrom(const > NameValuePairs &source) > CRYPTOPP_SET_FUNCTION_ENTRY(Prime2) > > CRYPTOPP_SET_FUNCTION_ENTRY(MultiplicativeInverseOfPrime2ModPrime1) > ; > + > +#ifdef CRYPTOPP_USE_RW_TWEAKED_ROOTS > + m_precompute = false; > +#endif > } > > NAMESPACE_END > diff --git a/rw.h b/rw.h > index 6820251..855d0d4 100644 > --- a/rw.h > +++ b/rw.h > @@ -48,8 +48,13 @@ class CRYPTOPP_DLL InvertibleRWFunction : public > RWFunction, public TrapdoorFunc > typedef InvertibleRWFunction ThisClass; > > public: > - void Initialize(const Integer &n, const Integer &p, const Integer > &q, const Integer &u) > - {m_n = n; m_p = p; m_q = q; m_u = u;} > +#ifdef CRYPTOPP_USE_RW_TWEAKED_ROOTS > + InvertibleRWFunction() : m_precompute(false), m_blinding(true) {} > +#else > + InvertibleRWFunction() : m_blinding(true) {} > +#endif > + > + void Initialize(const Integer &n, const Integer &p, const Integer > &q, const Integer &u, bool blinding = true); > // generate a random private key > void Initialize(RandomNumberGenerator &rng, unsigned int modulusBits) > {GenerateRandomWithKeySize(rng, modulusBits);} > @@ -74,13 +79,31 @@ public: > const Integer& GetPrime1() const {return m_p;} > const Integer& GetPrime2() const {return m_q;} > const Integer& GetMultiplicativeInverseOfPrime2ModPrime1() const > {return m_u;} > + bool GetEnableBlinding() const {return m_blinding;} > > void SetPrime1(const Integer &p) {m_p = p;} > void SetPrime2(const Integer &q) {m_q = q;} > void SetMultiplicativeInverseOfPrime2ModPrime1(const Integer &u) > {m_u = u;} > + void SetEnableBlinding(bool enabled) {m_blinding = enabled;} > + > +#ifdef CRYPTOPP_USE_RW_TWEAKED_ROOTS > + bool SupportsPrecomputation() const {return true;} > + void Precompute(unsigned int); > + void Precompute(unsigned int) const {return > const_cast<ThisClass*>(this)->Precompute(0);} > +#endif > + > +protected: > + void GenerateBlindingValue(RandomNumberGenerator& rng, Integer& > r, Integer& rInv) const; > > protected: > Integer m_p, m_q, m_u; > + > +#ifdef CRYPTOPP_USE_RW_TWEAKED_ROOTS > + Integer m_pre_2_9p, m_pre_2_3q, m_pre_q_p; > + bool m_precompute; > +#endif > + > + bool m_blinding; > }; > > //! RW > diff --git a/validat2.cpp b/validat2.cpp > index dd7ccd4..56a3df9 100644 > --- a/validat2.cpp > +++ b/validat2.cpp > @@ -515,12 +515,25 @@ bool ValidateRabin() > bool ValidateRW() > { > cout << "\nRW validation suite running...\n\n"; > + bool pass=true; > > - FileSource f("TestData/rw1024.dat", true, new HexDecoder); > - RWSS<PSSR, SHA>::Signer priv(f); > - RWSS<PSSR, SHA>::Verifier pub(priv); > + { > + FileSource f("TestData/rw1024.dat", true, new HexDecoder); > + RWSS<PSSR, SHA>::Signer priv(f); > + RWSS<PSSR, SHA>::Verifier pub(priv); > + pass = pass && SignatureValidate(priv, pub); > + } > + { > + cout << "Turning off blinding..." << endl; > > - return SignatureValidate(priv, pub); > + FileSource f("TestData/rw1024.dat", true, new HexDecoder); > + RWSS<PSSR, SHA>::Signer priv(f); > + priv.AccessKey().SetEnableBlinding(false); > + RWSS<PSSR, SHA>::Verifier pub(priv); > + pass = pass && SignatureValidate(priv, pub); > + } > + > + return pass; > } > > /* > > -- > -- > You received this message because you are subscribed to the "Crypto++ > Users" Google Group. > To unsubscribe, send an email to > [email protected]. > More information about Crypto++ and this group is available at > http://www.cryptopp.com. > --- > You received this message because you are subscribed to the Google > Groups "Crypto++ Users" group. > To unsubscribe from this group and stop receiving emails from it, send > an email to [email protected] > <mailto:[email protected]>. > For more options, visit https://groups.google.com/d/optout. -- -- You received this message because you are subscribed to the "Crypto++ Users" Google Group. To unsubscribe, send an email to [email protected]. More information about Crypto++ and this group is available at http://www.cryptopp.com. --- You received this message because you are subscribed to the Google Groups "Crypto++ Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. For more options, visit https://groups.google.com/d/optout.
smime.p7s
Description: S/MIME Cryptographic Signature
