Hello, I have backported the relevant commits to version 1.44 and the result is in the attached patches. The package builds fine but I have not tested it and I'm not sure how to properly test it... if you have suggestions, I'm happy to hear them.
I have asked an upstream developer (Peter Dettman) to review it. Cheers, -- Raphaël Hertzog ◈ Debian Developer Support Debian LTS: http://www.freexian.com/services/debian-lts.html Learn to master Debian: http://debian-handbook.info/get/
>From 5cb2f0578e6ec8f0d67e59d05d8c4704d8e05f83 Mon Sep 17 00:00:00 2001 From: Peter Dettman <peter.dett...@bouncycastle.org> Date: Tue, 22 Jul 2014 19:23:34 +0700 Subject: [PATCH] Add automatic EC point validation for decoded points and for multiplier outputs. Origin: upstream, https://github.com/bcgit/bc-java/commit/5cb2f05 Bug-Debian: https://bugs.debian.org/802671 Backporting notes of Raphaël Hertzog: * core/src/main/java/org/bouncycastle/ in current git was src/org/bouncycastle/ in 1.44 * DSTU4145PointEncoder.java does not exist in 1.44 (introduced in 158b54f). Dropped the changes. * AbstractECMultiplier.java does not exist in 1.44 but changes to AbstractECMultiplier.java mean that we must run ECAlgorithms.validatePoint() on any result of the multiply() function of any object implementing ECMultiplier. Done on: - FpNafMultiplier.java - ReferenceMultiplier.java - WNafMultiplier.java - WTauNafMultiplier.java * …/math/ec/custom/* were not present in 1.44. Dropped the corresponding changes. * Remaining changes have been manually backported: - ECPointTest.java: done - ReferenceMultiplier.java: done, added validatePoint() call on result - ECAlgorithms.java: done - ECPoint.java: done - Fp does not yet support getCompressionYTilde(), dropped from AbstractFp - F2m does not yet support checkCurveEquation() - dropped constructors accepting 4 params (with "zs") as ECPoint() does not support it, and dropped all code path that made use of this.zs since it's not available, basically everything related to non-affine coordinate system - ECCurve.java: - Hunk 1: validatePoint() not backported as there is no createPoint() call to replace. Instead ensure decodePoint() return value satisfies ECAlgorithms.validatePoint() - Hunk 2: no importPoint() (and no createPoint() usage found) - Hunk 3: useless (no-op change) - Hunk 4: useless (no-op change) - Hunk 5: validation on generated point at end of function - Hunk 6: done - Hunk 7: done (auto-applied) - Hunk 8/9: ECCurve is abstract and has no constructor, don't call parent constructors in Fp constructors (which happens in code from hunk 7 adding AbstractFp) - Hunk 10: ECCurve.Fp does not have decompressPoint() in 1.44, so the whole AbstractFp class was in fact useless, drop it and make Fp extends ECCurve again. End of hunk not applied, the AbstractF2m class is not needed as its sole purpose is to factorize a call to buildField() that version 1.44 does not have. - Hunk 11/12/13: Not applied as we don't introduce AbstractF2m. - Hunk 14: yp is already initialized as null in 1.44. - Hunk 15: decompressPoint() is really implemented differently... and even has different parameters. Just add the final check for yp==null and don't change the logic in the function. --- .../bouncycastle/asn1/ua/DSTU4145PointEncoder.java | 20 +- .../bouncycastle/math/ec/AbstractECMultiplier.java | 8 +- .../org/bouncycastle/math/ec/ECAlgorithms.java | 56 ++++- .../java/org/bouncycastle/math/ec/ECCurve.java | 183 +++++++++----- .../java/org/bouncycastle/math/ec/ECPoint.java | 270 ++++++++++++++------- .../bouncycastle/math/ec/ReferenceMultiplier.java | 28 +-- .../math/ec/custom/djb/Curve25519.java | 29 +-- .../math/ec/custom/djb/Curve25519Point.java | 17 +- .../math/ec/custom/sec/SecP192K1Curve.java | 33 +-- .../math/ec/custom/sec/SecP192K1Point.java | 19 +- .../math/ec/custom/sec/SecP192R1Curve.java | 29 +-- .../math/ec/custom/sec/SecP192R1Point.java | 19 +- .../math/ec/custom/sec/SecP224K1Curve.java | 33 +-- .../math/ec/custom/sec/SecP224K1Point.java | 19 +- .../math/ec/custom/sec/SecP224R1Curve.java | 29 +-- .../math/ec/custom/sec/SecP224R1Point.java | 18 +- .../math/ec/custom/sec/SecP256K1Curve.java | 33 +-- .../math/ec/custom/sec/SecP256K1Point.java | 19 +- .../math/ec/custom/sec/SecP256R1Curve.java | 29 +-- .../math/ec/custom/sec/SecP256R1Point.java | 18 +- .../math/ec/custom/sec/SecP384R1Curve.java | 29 +-- .../math/ec/custom/sec/SecP384R1Point.java | 18 +- .../math/ec/custom/sec/SecP521R1Curve.java | 29 +-- .../math/ec/custom/sec/SecP521R1Point.java | 18 +- .../org/bouncycastle/math/ec/test/ECPointTest.java | 33 +-- docs/releasenotes.html | 2 + 26 files changed, 401 insertions(+), 637 deletions(-) --- a/src/org/bouncycastle/math/ec/ECAlgorithms.java +++ b/src/org/bouncycastle/math/ec/ECAlgorithms.java @@ -24,7 +24,7 @@ public class ECAlgorithms // } // } - return implShamirsTrick(P, a, Q, b); + return ECAlgorithms.validatePoint(implShamirsTrick(P, a, Q, b)); } /* @@ -54,7 +54,7 @@ public class ECAlgorithms throw new IllegalArgumentException("P and Q must be on same curve"); } - return implShamirsTrick(P, k, Q, l); + return ECAlgorithms.validatePoint(implShamirsTrick(P, k, Q, l)); } private static ECPoint implShamirsTrick(ECPoint P, BigInteger k, @@ -90,4 +90,47 @@ public class ECAlgorithms return R; } + + /** + * Simple shift-and-add multiplication. Serves as reference implementation + * to verify (possibly faster) implementations, and for very small scalars. + * + * @param p + * The point to multiply. + * @param k + * The multiplier. + * @return The result of the point multiplication <code>kP</code>. + */ + public static ECPoint referenceMultiply(ECPoint p, BigInteger k) + { + BigInteger x = k.abs(); + ECPoint q = p.getCurve().getInfinity(); + int t = x.bitLength(); + if (t > 0) + { + if (x.testBit(0)) + { + q = p; + } + for (int i = 1; i < t; i++) + { + p = p.twice(); + if (x.testBit(i)) + { + q = q.add(p); + } + } + } + return k.signum() < 0 ? q.negate() : q; + } + + public static ECPoint validatePoint(ECPoint p) + { + if (!p.isValid()) + { + throw new IllegalArgumentException("Invalid point"); + } + + return p; + } } --- a/src/org/bouncycastle/math/ec/ECCurve.java +++ b/src/org/bouncycastle/math/ec/ECCurve.java @@ -134,7 +134,12 @@ public abstract class ECCurve throw new RuntimeException("Invalid point encoding 0x" + Integer.toString(encoded[0], 16)); } - return p; + if (encoded[0] != 0x00 && p.isInfinity()) + { + throw new IllegalArgumentException("Invalid infinity encoding"); + } + + return ECAlgorithms.validatePoint(p); } public ECPoint getInfinity() @@ -448,7 +453,7 @@ public abstract class ECCurve throw new RuntimeException("Invalid point encoding 0x" + Integer.toString(encoded[0], 16)); } - return p; + return ECAlgorithms.validatePoint(p); } public ECPoint getInfinity() @@ -542,6 +547,11 @@ public abstract class ECCurve } yp = xp.multiply(z); } + + if (yp == null) + { + throw new IllegalArgumentException("Invalid point compression"); + } return new ECPoint.F2m(this, xp, yp); } --- a/src/org/bouncycastle/math/ec/ECPoint.java +++ b/src/org/bouncycastle/math/ec/ECPoint.java @@ -27,7 +27,9 @@ public abstract class ECPoint this.x = x; this.y = y; } - + + protected abstract boolean satisfiesCurveEquation(); + public ECCurve getCurve() { return curve; @@ -53,6 +55,33 @@ public abstract class ECPoint return withCompression; } + public boolean isValid() + { + if (isInfinity()) + { + return true; + } + + // TODO Sanity-check the field elements + + ECCurve curve = getCurve(); + if (curve != null) + { + if (!satisfiesCurveEquation()) + { + return false; + } + + BigInteger h = curve.getH(); + if (h != null && ECAlgorithms.referenceMultiply(this, h).isInfinity()) + { + return false; + } + } + + return true; + } + public boolean equals( Object other) { @@ -147,10 +176,38 @@ public abstract class ECPoint return this.multiplier.multiply(this, k, preCompInfo); } + public static abstract class AbstractFp extends ECPoint + { + protected AbstractFp(ECCurve curve, ECFieldElement x, ECFieldElement y) + { + super(curve, x, y); + } + + protected boolean satisfiesCurveEquation() + { + ECFieldElement X = this.x, Y = this.y, A = curve.getA(), B = curve.getB(); + ECFieldElement lhs = Y.square(); + + ECFieldElement rhs = X.square().add(A).multiply(X).add(B); + return lhs.equals(rhs); + } + + public ECPoint subtract(ECPoint b) + { + if (b.isInfinity()) + { + return this; + } + + // Add -b + return add(b.negate()); + } + } + /** * Elliptic curve points over Fp */ - public static class Fp extends ECPoint + public static class Fp extends AbstractFp { /** @@ -166,7 +223,7 @@ public abstract class ECPoint } /** - * Create a point that encodes with or without point compresion. + * Create a point that encodes with or without point compression. * * @param curve the curve to use * @param x affine x co-ordinate @@ -292,18 +349,6 @@ public abstract class ECPoint return new ECPoint.Fp(curve, x3, y3, this.withCompression); } - // D.3.2 pg 102 (see Note:) - public ECPoint subtract(ECPoint b) - { - if (b.isInfinity()) - { - return this; - } - - // Add -b - return add(b.negate()); - } - public ECPoint negate() { return new ECPoint.Fp(curve, this.x, this.y.negate(), this.withCompression); @@ -322,10 +367,30 @@ public abstract class ECPoint // } } + public static abstract class AbstractF2m extends ECPoint + { + protected AbstractF2m(ECCurve curve, ECFieldElement x, ECFieldElement y) + { + super(curve, x, y); + } + + protected boolean satisfiesCurveEquation() + { + ECCurve curve = getCurve(); + ECFieldElement X = this.x, A = curve.getA(), B = curve.getB(); + + ECFieldElement Y = this.y; + ECFieldElement lhs = Y.add(X).multiply(Y); + + ECFieldElement rhs = X.add(A).multiply(X.square()).add(B); + return lhs.equals(rhs); + } + } + /** * Elliptic curve points over F2m */ - public static class F2m extends ECPoint + public static class F2m extends AbstractF2m { /** * @param curve base curve --- a/src/org/bouncycastle/math/ec/ReferenceMultiplier.java +++ b/src/org/bouncycastle/math/ec/ReferenceMultiplier.java @@ -4,27 +4,8 @@ import java.math.BigInteger; class ReferenceMultiplier implements ECMultiplier { - /** - * Simple shift-and-add multiplication. Serves as reference implementation - * to verify (possibly faster) implementations in - * {@link org.bouncycastle.math.ec.ECPoint ECPoint}. - * - * @param p The point to multiply. - * @param k The factor by which to multiply. - * @return The result of the point multiplication <code>k * p</code>. - */ public ECPoint multiply(ECPoint p, BigInteger k, PreCompInfo preCompInfo) { - ECPoint q = p.getCurve().getInfinity(); - int t = k.bitLength(); - for (int i = 0; i < t; i++) - { - if (k.testBit(i)) - { - q = q.add(p); - } - p = p.twice(); - } - return q; + return ECAlgorithms.validatePoint(ECAlgorithms.referenceMultiply(p, k)); } } --- a/test/src/org/bouncycastle/math/ec/test/ECPointTest.java +++ b/test/src/org/bouncycastle/math/ec/test/ECPointTest.java @@ -13,6 +13,7 @@ import org.bouncycastle.asn1.x9.X9ECPara import org.bouncycastle.math.ec.ECCurve; import org.bouncycastle.math.ec.ECFieldElement; import org.bouncycastle.math.ec.ECPoint; +import org.bouncycastle.math.ec.ECAlgorithms; /** * Test class for {@link org.bouncycastle.math.ec.ECPoint ECPoint}. All @@ -263,32 +264,6 @@ public class ECPointTest extends TestCas } /** - * Simple shift-and-add multiplication. Serves as reference implementation - * to verify (possibly faster) implementations in - * {@link org.bouncycastle.math.ec.ECPoint ECPoint}. - * - * @param p - * The point to multiply. - * @param k - * The multiplier. - * @return The result of the point multiplication <code>kP</code>. - */ - private ECPoint multiply(ECPoint p, BigInteger k) - { - ECPoint q = p.getCurve().getInfinity(); - int t = k.bitLength(); - for (int i = 0; i < t; i++) - { - if (k.testBit(i)) - { - q = q.add(p); - } - p = p.twice(); - } - return q; - } - - /** * Checks, if the point multiplication algorithm of the given point yields * the same result as point multiplication done by the reference * implementation given in <code>multiply()</code>. This method chooses a @@ -303,7 +278,7 @@ public class ECPointTest extends TestCas private void implTestMultiply(ECPoint p, int numBits) { BigInteger k = new BigInteger(numBits, secRand); - ECPoint ref = multiply(p, k); + ECPoint ref = org.bouncycastle.math.ec.ECAlgorithms.referenceMultiply(p, k); ECPoint q = p.multiply(k); assertEquals("ECPoint.multiply is incorrect", ref, q); } @@ -327,7 +302,7 @@ public class ECPointTest extends TestCas do { - ECPoint ref = multiply(p, k); + ECPoint ref = org.bouncycastle.math.ec.ECAlgorithms.referenceMultiply(p, k); ECPoint q = p.multiply(k); assertEquals("ECPoint.multiply is incorrect", ref, q); k = k.add(BigInteger.ONE); --- a/src/org/bouncycastle/math/ec/FpNafMultiplier.java +++ b/src/org/bouncycastle/math/ec/FpNafMultiplier.java @@ -34,6 +34,6 @@ class FpNafMultiplier implements ECMulti } } - return R; + return ECAlgorithms.validatePoint(R); } } --- a/src/org/bouncycastle/math/ec/WNafMultiplier.java +++ b/src/org/bouncycastle/math/ec/WNafMultiplier.java @@ -234,7 +234,7 @@ class WNafMultiplier implements ECMultip wnafPreCompInfo.setPreComp(preComp); wnafPreCompInfo.setTwiceP(twiceP); p.setPreCompInfo(wnafPreCompInfo); - return q; + return ECAlgorithms.validatePoint(q); } } --- a/src/org/bouncycastle/math/ec/WTauNafMultiplier.java +++ b/src/org/bouncycastle/math/ec/WTauNafMultiplier.java @@ -34,7 +34,7 @@ class WTauNafMultiplier implements ECMul ZTauElement rho = Tnaf.partModReduction(k, m, a, s, mu, (byte)10); - return multiplyWTnaf(p, rho, preCompInfo, a, mu); + return ECAlgorithms.validatePoint(multiplyWTnaf(p, rho, preCompInfo, a, mu)); } /**
>From e25e94a046a6934819133886439984e2fecb2b04 Mon Sep 17 00:00:00 2001 From: Peter Dettman <peter.dett...@bouncycastle.org> Date: Fri, 25 Jul 2014 14:46:07 +0700 Subject: [PATCH] Add cofactor validation after point decompression Origin: upstream, https://github.com/bcgit/bc-java/commit/e25e94a Bug-Debian: https://bugs.debian.org/802671 Backporting notes of Raphaël Hertzog: * ECCurve.java: - Hunk 1: decompressPoint() does not exist on ECCurve.Fp, dropped. - Hunk 2: drop variable rename, keep only final p.satisfiesCofactor() check Replaced getCofactor() with getH() since the former does not exist yet. But getH() was only available on F2m, added a default implementation returning null to ECCurve (this is what happens with newer versions when you create an Fp curve without specifying the cofactor). * ECPoint.java: done, noted that satisfiesCofactor() adds a supplementary check compared to version 1.44 (h.equals(ECConstants.ONE)) --- .../java/org/bouncycastle/math/ec/ECCurve.java | 29 +++++++++++++++------- .../java/org/bouncycastle/math/ec/ECPoint.java | 10 +++++--- 2 files changed, 27 insertions(+), 12 deletions(-) --- a/src/org/bouncycastle/math/ec/ECCurve.java +++ b/src/org/bouncycastle/math/ec/ECCurve.java @@ -30,6 +30,12 @@ public abstract class ECCurve return b; } + public BigInteger getH() + { + // ECCurve without cofactor by default, overriden by subclasses + return null; + } + /** * Elliptic curve over Fp */ @@ -553,7 +559,13 @@ public abstract class ECCurve throw new IllegalArgumentException("Invalid point compression"); } - return new ECPoint.F2m(this, xp, yp); + ECPoint p = new ECPoint.F2m(this, xp, yp); + if (!p.satisfiesCofactor()) + { + throw new IllegalArgumentException("Invalid point"); + } + + return p; } /** --- a/src/org/bouncycastle/math/ec/ECPoint.java +++ b/src/org/bouncycastle/math/ec/ECPoint.java @@ -28,6 +28,12 @@ public abstract class ECPoint this.y = y; } + protected boolean satisfiesCofactor() + { + BigInteger h = curve.getH(); + return h == null || h.equals(ECConstants.ONE) || !ECAlgorithms.referenceMultiply(this, h).isInfinity(); + } + protected abstract boolean satisfiesCurveEquation(); public ECCurve getCurve() @@ -72,8 +78,7 @@ public abstract class ECPoint return false; } - BigInteger h = curve.getH(); - if (h != null && ECAlgorithms.referenceMultiply(this, h).isInfinity()) + if (!satisfiesCofactor()) { return false; }
