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;
             }
__
This is the maintainer address of Debian's Java team
<http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/pkg-java-maintainers>. 
Please use
debian-j...@lists.debian.org for discussions and questions.

Reply via email to