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].
For more options, visit https://groups.google.com/d/optout.
