Home | History | Annotate | Download | only in testcases 
      1 /**
      2  * @license
      3  * Copyright 2016 Google Inc. All rights reserved.
      4  * Licensed under the Apache License, Version 2.0 (the "License");
      5  * you may not use this file except in compliance with the License.
      6  * You may obtain a copy of the License at
      7  *
      8  *   http://www.apache.org/licenses/LICENSE-2.0
      9  *
     10  * Unless required by applicable law or agreed to in writing, software
     11  * distributed under the License is distributed on an "AS IS" BASIS,
     12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     13  * See the License for the specific language governing permissions and
     14  * limitations under the License.
     15  */
     16 
     17 // TODO(bleichen):
     18 // - add tests for SHA1WithDSA with wrong key
     19 // - add tests for "alternative" algorithm names
     20 // - convert tests for deterministic DSA variants.
     21 //   Deterministic DSA has a few new drawbacks:
     22 //     * implementations flaws that generate k incorrectly can leak
     23 //       the key if multiple implementations (e.g. one correct one incorrect)
     24 //       is used.
     25 //     * timing attacks are more serious if the attacker can ask for the same
     26 //       signature multiple times, since this allows to get more accurate timings.
     27 package com.google.security.wycheproof;
     28 
     29 import com.google.security.wycheproof.WycheproofRunner.ProviderType;
     30 import com.google.security.wycheproof.WycheproofRunner.SlowTest;
     31 // Android-removed: Android doesn't support JMX
     32 // import java.lang.management.ManagementFactory;
     33 // import java.lang.management.ThreadMXBean;
     34 import java.math.BigInteger;
     35 import java.security.GeneralSecurityException;
     36 import java.security.KeyFactory;
     37 import java.security.KeyPair;
     38 import java.security.KeyPairGenerator;
     39 import java.security.MessageDigest;
     40 import java.security.NoSuchAlgorithmException;
     41 import java.security.PublicKey;
     42 import java.security.Signature;
     43 import java.security.SignatureException;
     44 import java.security.interfaces.DSAParams;
     45 import java.security.interfaces.DSAPrivateKey;
     46 import java.security.interfaces.DSAPublicKey;
     47 import java.security.spec.DSAPrivateKeySpec;
     48 import java.security.spec.DSAPublicKeySpec;
     49 import java.util.Arrays;
     50 import javax.crypto.Cipher;
     51 import junit.framework.TestCase;
     52 
     53 /**
     54  * Tests DSA against invalid signatures. The motivation for this test is the DSA implementation in
     55  * gpg4browsers. This implementation accepts signatures with r=1 and s=0 as valid.
     56  *
     57  * @author bleichen (at) google.com (Daniel Bleichenbacher)
     58  */
     59 public class DsaTest extends TestCase {
     60   static final String MESSAGE = "Hello";
     61 
     62   static final DSAPrivateKeySpec privateKey1 =
     63       new DSAPrivateKeySpec(
     64           // x
     65           new BigInteger("15382583218386677486843706921635237927801862255437148328980464126979"),
     66           // p
     67           new BigInteger(
     68               "181118486631420055711787706248812146965913392568235070235446058914"
     69                   + "1170708161715231951918020125044061516370042605439640379530343556"
     70                   + "4101919053459832890139496933938670005799610981765220283775567361"
     71                   + "4836626483403394052203488713085936276470766894079318754834062443"
     72                   + "1033792580942743268186462355159813630244169054658542719322425431"
     73                   + "4088256212718983105131138772434658820375111735710449331518776858"
     74                   + "7867938758654181244292694091187568128410190746310049564097068770"
     75                   + "8161261634790060655580211122402292101772553741704724263582994973"
     76                   + "9109274666495826205002104010355456981211025738812433088757102520"
     77                   + "562459649777989718122219159982614304359"),
     78           // q
     79           new BigInteger("19689526866605154788513693571065914024068069442724893395618704484701"),
     80           // g
     81           new BigInteger(
     82               "2859278237642201956931085611015389087970918161297522023542900348"
     83                   + "0877180630984239764282523693409675060100542360520959501692726128"
     84                   + "3149190229583566074777557293475747419473934711587072321756053067"
     85                   + "2532404847508798651915566434553729839971841903983916294692452760"
     86                   + "2490198571084091890169933809199002313226100830607842692992570749"
     87                   + "0504363602970812128803790973955960534785317485341020833424202774"
     88                   + "0275688698461842637641566056165699733710043802697192696426360843"
     89                   + "1736206792141319514001488556117408586108219135730880594044593648"
     90                   + "9237302749293603778933701187571075920849848690861126195402696457"
     91                   + "4111219599568903257472567764789616958430"));
     92 
     93   static final DSAPublicKeySpec publicKey1 =
     94       new DSAPublicKeySpec(
     95           new BigInteger(
     96               "3846308446317351758462473207111709291533523711306097971550086650"
     97                   + "2577333637930103311673872185522385807498738696446063139653693222"
     98                   + "3528823234976869516765207838304932337200968476150071617737755913"
     99                   + "3181601169463467065599372409821150709457431511200322947508290005"
    100                   + "1780020974429072640276810306302799924668893998032630777409440831"
    101                   + "4314588994475223696460940116068336991199969153649625334724122468"
    102                   + "7497038281983541563359385775312520539189474547346202842754393945"
    103                   + "8755803223951078082197762886933401284142487322057236814878262166"
    104                   + "5072306622943221607031324846468109901964841479558565694763440972"
    105                   + "5447389416166053148132419345627682740529"),
    106           privateKey1.getP(),
    107           privateKey1.getQ(),
    108           privateKey1.getG());
    109 
    110   // Signatures for Key1.
    111   static final String[] VALID_SIGNATURES = {
    112     "303d021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd"
    113         + "021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8786236",
    114   };
    115 
    116   /**
    117    * The following test vectos are derived from a valid signature by
    118    * using alternative BER encoding as well as legacy formats.
    119    * Accepting such signatures is in many cases benign. Hence the tests
    120    * below will pass if such signatures are accepted as valid.
    121    * The test vectors could be used to check for signature malleability.
    122    * An example where this kind of signature malleability was a problem is
    123    * https://en.bitcoin.it/wiki/Transaction_Malleability
    124    */
    125   static final String[] MODIFIED_SIGNATURES = {
    126     // BER:long form encoding of length
    127     "30813d021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9"
    128         + "cd021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8786236",
    129     "303e02811c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9"
    130         + "cd021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8786236",
    131     "303e021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd"
    132         + "02811d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8786236",
    133     // BER:length contains leading 0
    134     "3082003d021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8"
    135         + "c9cd021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe87862"
    136         + "36",
    137     "303f0282001c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8"
    138         + "c9cd021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe87862"
    139         + "36",
    140     "303f021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd"
    141         + "0282001d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe87862"
    142         + "36",
    143     // BER:prepending 0's to integer
    144     "303f021e00001e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8"
    145         + "c9cd021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe87862"
    146         + "36",
    147     "303f021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd"
    148         + "021f000000ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe87862"
    149         + "36",
    150     // The Sun provider accepts DSA signatures where a leading 00 has
    151     // been omitted in the ASN encoding.
    152     "303c021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd"
    153         + "021cade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8786236",
    154   };
    155 
    156   /**
    157    * The following test vectors are invalid DSA signatures.
    158    * According to {@link java.security.Signature#verify(byte[])} verifying an invalid
    159    * signature may either return false or throw a SignatureException.
    160    * We expect that a correct implementation of DSA signatures satisfies this contract.
    161    * Throwing a RuntimeException instead of a SignatureException could for example
    162    * result in a denial of service attack.
    163    *
    164    * <p>A list of problems that are caught by these signatures:
    165    * <li> CVE-2016-5546: OpenJDK8 throwed java.lang.ArrayIndexOutOfBoundsException for
    166    * some invalid DSA signatures.
    167    * </ul>
    168    */
    169   static final String[] INVALID_SIGNATURES = {
    170     // wrong length
    171     "303e021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd"
    172         + "021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8786236",
    173     "303c021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd"
    174         + "021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8786236",
    175     "303d021d1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd"
    176         + "021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8786236",
    177     "303d021b1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd"
    178         + "021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8786236",
    179     "303d021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd"
    180         + "021e00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8786236",
    181     "303d021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd"
    182         + "021c00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8786236",
    183     // uint32 overflow in length
    184     "3085010000003d021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916"
    185         + "173bb8c9cd021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813f"
    186         + "e8786236",
    187     "30420285010000001c1e41b479ad576905b960fe14eadb91b0ccf34843dab916"
    188         + "173bb8c9cd021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813f"
    189         + "e8786236",
    190     "3042021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd"
    191         + "0285010000001d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813f"
    192         + "e8786236",
    193     // uint64 overflow in length
    194     "308901000000000000003d021c1e41b479ad576905b960fe14eadb91b0ccf348"
    195         + "43dab916173bb8c9cd021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf"
    196         + "3365813fe8786236",
    197     "3046028901000000000000001c1e41b479ad576905b960fe14eadb91b0ccf348"
    198         + "43dab916173bb8c9cd021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf"
    199         + "3365813fe8786236",
    200     "3046021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd"
    201         + "028901000000000000001d00ade65988d237d30f9ef41dd424a4e1c8f16967cf"
    202         + "3365813fe8786236",
    203     // length = 2**31 - 1
    204     "30847fffffff021c1e41b479ad576905b960fe14eadb91b0ccf34843dab91617"
    205         + "3bb8c9cd021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8"
    206         + "786236",
    207     "304102847fffffff1e41b479ad576905b960fe14eadb91b0ccf34843dab91617"
    208         + "3bb8c9cd021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8"
    209         + "786236",
    210     "3041021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd"
    211         + "02847fffffff00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8"
    212         + "786236",
    213     // length = 2**32 - 1
    214     "3084ffffffff021c1e41b479ad576905b960fe14eadb91b0ccf34843dab91617"
    215         + "3bb8c9cd021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8"
    216         + "786236",
    217     "30410284ffffffff1e41b479ad576905b960fe14eadb91b0ccf34843dab91617"
    218         + "3bb8c9cd021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8"
    219         + "786236",
    220     "3041021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd"
    221         + "0284ffffffff00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8"
    222         + "786236",
    223     // length = 2**64 - 1
    224     "3088ffffffffffffffff021c1e41b479ad576905b960fe14eadb91b0ccf34843"
    225         + "dab916173bb8c9cd021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf33"
    226         + "65813fe8786236",
    227     "30450288ffffffffffffffff1e41b479ad576905b960fe14eadb91b0ccf34843"
    228         + "dab916173bb8c9cd021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf33"
    229         + "65813fe8786236",
    230     "3045021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd"
    231         + "0288ffffffffffffffff00ade65988d237d30f9ef41dd424a4e1c8f16967cf33"
    232         + "65813fe8786236",
    233     // removing sequence
    234     "",
    235     // appending 0's to sequence
    236     "303f021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd"
    237         + "021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe878623600"
    238         + "00",
    239     // prepending 0's to sequence
    240     "303f0000021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8"
    241         + "c9cd021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe87862"
    242         + "36",
    243     // appending unused 0's
    244     "303f021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd"
    245         + "0000021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe87862"
    246         + "36",
    247     // appending null value
    248     "303f021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd"
    249         + "021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe878623605"
    250         + "00",
    251     "303f021e1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd"
    252         + "0500021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe87862"
    253         + "36",
    254     "303f021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd"
    255         + "021f00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe878623605"
    256         + "00",
    257     // including garbage
    258     "3042498177303d021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916"
    259         + "173bb8c9cd021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813f"
    260         + "e8786236",
    261     "30412500303d021c1e41b479ad576905b960fe14eadb91b0ccf34843dab91617"
    262         + "3bb8c9cd021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8"
    263         + "786236",
    264     "303f303d021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8"
    265         + "c9cd021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe87862"
    266         + "360004deadbeef",
    267     "30422221498177021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916"
    268         + "173bb8c9cd021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813f"
    269         + "e8786236",
    270     "304122202500021c1e41b479ad576905b960fe14eadb91b0ccf34843dab91617"
    271         + "3bb8c9cd021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8"
    272         + "786236",
    273     "3045221e021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8"
    274         + "c9cd0004deadbeef021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf33"
    275         + "65813fe8786236",
    276     "3042021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd"
    277         + "2222498177021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813f"
    278         + "e8786236",
    279     "3041021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd"
    280         + "22212500021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8"
    281         + "786236",
    282     "3045021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd"
    283         + "221f021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe87862"
    284         + "360004deadbeef",
    285     // including undefined tags
    286     "3045aa00bb00cd00303d021c1e41b479ad576905b960fe14eadb91b0ccf34843"
    287         + "dab916173bb8c9cd021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf33"
    288         + "65813fe8786236",
    289     "3043aa02aabb303d021c1e41b479ad576905b960fe14eadb91b0ccf34843dab9"
    290         + "16173bb8c9cd021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf336581"
    291         + "3fe8786236",
    292     "30452224aa00bb00cd00021c1e41b479ad576905b960fe14eadb91b0ccf34843"
    293         + "dab916173bb8c9cd021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf33"
    294         + "65813fe8786236",
    295     "30432222aa02aabb021c1e41b479ad576905b960fe14eadb91b0ccf34843dab9"
    296         + "16173bb8c9cd021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf336581"
    297         + "3fe8786236",
    298     "3045021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd"
    299         + "2225aa00bb00cd00021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf33"
    300         + "65813fe8786236",
    301     "3043021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd"
    302         + "2223aa02aabb021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf336581"
    303         + "3fe8786236",
    304     // changing tag value
    305     "2e3d021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd"
    306         + "021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8786236",
    307     "323d021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd"
    308         + "021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8786236",
    309     "ff3d021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd"
    310         + "021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8786236",
    311     "303d001c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd"
    312         + "021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8786236",
    313     "303d041c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd"
    314         + "021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8786236",
    315     "303dff1c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd"
    316         + "021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8786236",
    317     "303d021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd"
    318         + "001d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8786236",
    319     "303d021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd"
    320         + "041d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8786236",
    321     "303d021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd"
    322         + "ff1d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8786236",
    323     // dropping value of sequence
    324     "3000",
    325     // using composition
    326     "3041300102303c1c1e41b479ad576905b960fe14eadb91b0ccf34843dab91617"
    327         + "3bb8c9cd021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8"
    328         + "786236",
    329     "3041222002011e021b41b479ad576905b960fe14eadb91b0ccf34843dab91617"
    330         + "3bb8c9cd021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8"
    331         + "786236",
    332     "3041021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd"
    333         + "2221020100021cade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8"
    334         + "786236",
    335     // truncate sequence
    336     "303c021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd"
    337         + "021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe87862",
    338     "303c1c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd02"
    339         + "1d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8786236",
    340     // indefinite length with no delimiter
    341     "3080021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd"
    342         + "021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8786236",
    343     // prepend empty sequence
    344     "303f3000021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8"
    345         + "c9cd021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe87862"
    346         + "36",
    347     // append empty sequence
    348     "303f021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd"
    349         + "021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe878623630"
    350         + "00",
    351     // sequence of sequence
    352     "303f303d021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8"
    353         + "c9cd021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe87862"
    354         + "36",
    355     // truncated sequence
    356     "301e021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd",
    357     // repeat element in sequence
    358     "305c021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd"
    359         + "021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe878623602"
    360         + "1d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8786236",
    361     // removing integer
    362     "301f021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8786236",
    363     // appending 0's to integer
    364     "303f021e1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd"
    365         + "0000021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe87862"
    366         + "36",
    367     "303f021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd"
    368         + "021f00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe878623600"
    369         + "00",
    370     // dropping value of integer
    371     "30210200021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8786236",
    372     "3020021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd0200",
    373     // modify first byte of integer
    374     "303d021c1f41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd"
    375         + "021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8786236",
    376     "303d021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd"
    377         + "021d01ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8786236",
    378     // modify last byte of integer
    379     "303d021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cc"
    380         + "021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8786236",
    381     "303d021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd"
    382         + "021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8786237",
    383     // truncate integer
    384     "303c021b1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c902"
    385         + "1d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8786236",
    386     "303c021b41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd02"
    387         + "1d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8786236",
    388     "303c021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd"
    389         + "021c00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe87862",
    390     // leading ff in integer
    391     "303e021dff1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9"
    392         + "cd021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8786236",
    393     "303e021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd"
    394         + "021eff00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8786236",
    395     // infinity
    396     "3022090180021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8786236",
    397     "3021021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd090180",
    398     // Vectors where r or s have been modified e.g. by adding or subtracting the order of the
    399     // group and hence violate the range check for r and s required by DSA.
    400     "303d021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd"
    401         + "021d0168dcf02f57b0caef7ddc183bee1ca94ee09c1a02ee4b0200a54dcb93",
    402     "303c021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd"
    403         + "021cf2efc2e24cbedb2fc00c236c5b2d1a430236b59b7880007f2ba2f8d9",
    404     "303d021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd"
    405         + "021dff5219a6772dc82cf0610be22bdb5b1e370e969830cc9a7ec017879dca",
    406     "303d021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd"
    407         + "021d01ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8786236",
    408     "303e021d00d9384b2032d060e59848f87cb4535936bc25fa77959e96d7f88e33"
    409         + "2a021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8786236",
    410     "303e021d00d9384b2032d060e59848f87cb4535936bc25fa77959e96d7f88e33"
    411         + "2a021d0168dcf02f57b0caef7ddc183bee1ca94ee09c1a02ee4b0200a54dcb93",
    412     "303d021d00d9384b2032d060e59848f87cb4535936bc25fa77959e96d7f88e33"
    413         + "2a021cf2efc2e24cbedb2fc00c236c5b2d1a430236b59b7880007f2ba2f8d9",
    414     "303e021d00d9384b2032d060e59848f87cb4535936bc25fa77959e96d7f88e33"
    415         + "2a021dff5219a6772dc82cf0610be22bdb5b1e370e969830cc9a7ec017879dca",
    416     "303e021d00d9384b2032d060e59848f87cb4535936bc25fa77959e96d7f88e33"
    417         + "2a021d01ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8786236",
    418     "303e021dff634b1dd327de7125da7903ad2163ca2addc096101fd395567ee360"
    419         + "70021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8786236",
    420     "303e021dff634b1dd327de7125da7903ad2163ca2addc096101fd395567ee360"
    421         + "70021d0168dcf02f57b0caef7ddc183bee1ca94ee09c1a02ee4b0200a54dcb93",
    422     "303d021dff634b1dd327de7125da7903ad2163ca2addc096101fd395567ee360"
    423         + "70021cf2efc2e24cbedb2fc00c236c5b2d1a430236b59b7880007f2ba2f8d9",
    424     "303e021dff634b1dd327de7125da7903ad2163ca2addc096101fd395567ee360"
    425         + "70021dff5219a6772dc82cf0610be22bdb5b1e370e969830cc9a7ec017879dca",
    426     "303e021dff634b1dd327de7125da7903ad2163ca2addc096101fd395567ee360"
    427         + "70021d01ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8786236",
    428     "303d021ce1be4b8652a896fa469f01eb15246e4f330cb7bc2546e9e8c4473633"
    429         + "021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8786236",
    430     "303d021ce1be4b8652a896fa469f01eb15246e4f330cb7bc2546e9e8c4473633"
    431         + "021d0168dcf02f57b0caef7ddc183bee1ca94ee09c1a02ee4b0200a54dcb93",
    432     "303c021ce1be4b8652a896fa469f01eb15246e4f330cb7bc2546e9e8c4473633"
    433         + "021cf2efc2e24cbedb2fc00c236c5b2d1a430236b59b7880007f2ba2f8d9",
    434     "303d021ce1be4b8652a896fa469f01eb15246e4f330cb7bc2546e9e8c4473633"
    435         + "021dff5219a6772dc82cf0610be22bdb5b1e370e969830cc9a7ec017879dca",
    436     "303d021ce1be4b8652a896fa469f01eb15246e4f330cb7bc2546e9e8c4473633"
    437         + "021d01ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8786236",
    438     "303e021d011e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9"
    439         + "cd021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8786236",
    440     "303e021d011e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9"
    441         + "cd021d0168dcf02f57b0caef7ddc183bee1ca94ee09c1a02ee4b0200a54dcb93",
    442     "303d021d011e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9"
    443         + "cd021cf2efc2e24cbedb2fc00c236c5b2d1a430236b59b7880007f2ba2f8d9",
    444     "303e021d011e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9"
    445         + "cd021dff5219a6772dc82cf0610be22bdb5b1e370e969830cc9a7ec017879dca",
    446     "303e021d011e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9"
    447         + "cd021d01ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8786236",
    448     // Signatures with special case values for r and s. E.g. r=1, s=0 are values that can lead to
    449     // forgeries if the DSA implementation does not check boundaries and computes s^(-1) == 0.
    450     "3022020100021dff450969597a870820211805983688387a10cd4dcc451a7f3f432a96a3",
    451     "3006020100020101",
    452     "30060201000201ff",
    453     "3022020100021d00baf696a68578f7dfdee7fa67c977c785ef32b233bae580c0bcd5695d",
    454     "3022020100021d00baf696a68578f7dfdee7fa67c977c785ef32b233bae580c0bcd5695e",
    455     "3022020100021d0100000000000000000000000000000000000000000000000000000000",
    456     "3082010802010002820101008f7935d9b9aae9bfabed887acf4951b6f32ec59e"
    457         + "3baf3718e8eac4961f3efd3606e74351a9c4183339b809e7c2ae1c539ba7475b"
    458         + "85d011adb8b47987754984695cac0e8f14b3360828a22ffa27110a3d62a99345"
    459         + "3409a0fe696c4658f84bdd20819c3709a01057b195adcd00233dba5484b6291f"
    460         + "9d648ef883448677979cec04b434a6ac2e75e9985de23db0292fc1118c9ffa9d"
    461         + "8181e7338db792b730d7b9e349592f68099872153915ea3d6b8b4653c633458f"
    462         + "803b32a4c2e0f27290256e4e3f8a3b0838a1c450e4e18c1a29a37ddf5ea143de"
    463         + "4b66ff04903ed5cf1623e158d487c608e97f211cd81dca23cb6e380765f822e3"
    464         + "42be484c05763939601cd667",
    465     "3008020100090380fe01",
    466     "3022020101021dff450969597a870820211805983688387a10cd4dcc451a7f3f432a96a3",
    467     "3006020101020101",
    468     "30060201010201ff",
    469     "3022020101021d00baf696a68578f7dfdee7fa67c977c785ef32b233bae580c0bcd5695d",
    470     "3022020101021d00baf696a68578f7dfdee7fa67c977c785ef32b233bae580c0bcd5695e",
    471     "3022020101021d0100000000000000000000000000000000000000000000000000000000",
    472     "3082010802010102820101008f7935d9b9aae9bfabed887acf4951b6f32ec59e"
    473         + "3baf3718e8eac4961f3efd3606e74351a9c4183339b809e7c2ae1c539ba7475b"
    474         + "85d011adb8b47987754984695cac0e8f14b3360828a22ffa27110a3d62a99345"
    475         + "3409a0fe696c4658f84bdd20819c3709a01057b195adcd00233dba5484b6291f"
    476         + "9d648ef883448677979cec04b434a6ac2e75e9985de23db0292fc1118c9ffa9d"
    477         + "8181e7338db792b730d7b9e349592f68099872153915ea3d6b8b4653c633458f"
    478         + "803b32a4c2e0f27290256e4e3f8a3b0838a1c450e4e18c1a29a37ddf5ea143de"
    479         + "4b66ff04903ed5cf1623e158d487c608e97f211cd81dca23cb6e380765f822e3"
    480         + "42be484c05763939601cd667",
    481     "3008020101090380fe01",
    482     "30220201ff021dff450969597a870820211805983688387a10cd4dcc451a7f3f432a96a3",
    483     "30060201ff020101",
    484     "30060201ff0201ff",
    485     "30220201ff021d00baf696a68578f7dfdee7fa67c977c785ef32b233bae580c0bcd5695d",
    486     "30220201ff021d00baf696a68578f7dfdee7fa67c977c785ef32b233bae580c0bcd5695e",
    487     "30220201ff021d0100000000000000000000000000000000000000000000000000000000",
    488     "308201080201ff02820101008f7935d9b9aae9bfabed887acf4951b6f32ec59e"
    489         + "3baf3718e8eac4961f3efd3606e74351a9c4183339b809e7c2ae1c539ba7475b"
    490         + "85d011adb8b47987754984695cac0e8f14b3360828a22ffa27110a3d62a99345"
    491         + "3409a0fe696c4658f84bdd20819c3709a01057b195adcd00233dba5484b6291f"
    492         + "9d648ef883448677979cec04b434a6ac2e75e9985de23db0292fc1118c9ffa9d"
    493         + "8181e7338db792b730d7b9e349592f68099872153915ea3d6b8b4653c633458f"
    494         + "803b32a4c2e0f27290256e4e3f8a3b0838a1c450e4e18c1a29a37ddf5ea143de"
    495         + "4b66ff04903ed5cf1623e158d487c608e97f211cd81dca23cb6e380765f822e3"
    496         + "42be484c05763939601cd667",
    497     "30080201ff090380fe01",
    498     "303e021d00baf696a68578f7dfdee7fa67c977c785ef32b233bae580c0bcd569"
    499         + "5d021dff450969597a870820211805983688387a10cd4dcc451a7f3f432a96a3",
    500     "3022021d00baf696a68578f7dfdee7fa67c977c785ef32b233bae580c0bcd5695d020100",
    501     "3022021d00baf696a68578f7dfdee7fa67c977c785ef32b233bae580c0bcd5695d020101",
    502     "3022021d00baf696a68578f7dfdee7fa67c977c785ef32b233bae580c0bcd5695d0201ff",
    503     "303e021d00baf696a68578f7dfdee7fa67c977c785ef32b233bae580c0bcd569"
    504         + "5d021d00baf696a68578f7dfdee7fa67c977c785ef32b233bae580c0bcd5695d",
    505     "303e021d00baf696a68578f7dfdee7fa67c977c785ef32b233bae580c0bcd569"
    506         + "5d021d00baf696a68578f7dfdee7fa67c977c785ef32b233bae580c0bcd5695e",
    507     "303e021d00baf696a68578f7dfdee7fa67c977c785ef32b233bae580c0bcd569"
    508         + "5d021d0100000000000000000000000000000000000000000000000000000000",
    509     "30820124021d00baf696a68578f7dfdee7fa67c977c785ef32b233bae580c0bc"
    510         + "d5695d02820101008f7935d9b9aae9bfabed887acf4951b6f32ec59e3baf3718"
    511         + "e8eac4961f3efd3606e74351a9c4183339b809e7c2ae1c539ba7475b85d011ad"
    512         + "b8b47987754984695cac0e8f14b3360828a22ffa27110a3d62a993453409a0fe"
    513         + "696c4658f84bdd20819c3709a01057b195adcd00233dba5484b6291f9d648ef8"
    514         + "83448677979cec04b434a6ac2e75e9985de23db0292fc1118c9ffa9d8181e733"
    515         + "8db792b730d7b9e349592f68099872153915ea3d6b8b4653c633458f803b32a4"
    516         + "c2e0f27290256e4e3f8a3b0838a1c450e4e18c1a29a37ddf5ea143de4b66ff04"
    517         + "903ed5cf1623e158d487c608e97f211cd81dca23cb6e380765f822e342be484c"
    518         + "05763939601cd667",
    519     "3024021d00baf696a68578f7dfdee7fa67c977c785ef32b233bae580c0bcd5695d090380fe01",
    520     "303e021d00baf696a68578f7dfdee7fa67c977c785ef32b233bae580c0bcd569"
    521         + "5e021dff450969597a870820211805983688387a10cd4dcc451a7f3f432a96a3",
    522     "3022021d00baf696a68578f7dfdee7fa67c977c785ef32b233bae580c0bcd5695e020100",
    523     "3022021d00baf696a68578f7dfdee7fa67c977c785ef32b233bae580c0bcd5695e020101",
    524     "3022021d00baf696a68578f7dfdee7fa67c977c785ef32b233bae580c0bcd5695e0201ff",
    525     "303e021d00baf696a68578f7dfdee7fa67c977c785ef32b233bae580c0bcd569"
    526         + "5e021d00baf696a68578f7dfdee7fa67c977c785ef32b233bae580c0bcd5695d",
    527     "303e021d00baf696a68578f7dfdee7fa67c977c785ef32b233bae580c0bcd569"
    528         + "5e021d00baf696a68578f7dfdee7fa67c977c785ef32b233bae580c0bcd5695e",
    529     "303e021d00baf696a68578f7dfdee7fa67c977c785ef32b233bae580c0bcd569"
    530         + "5e021d0100000000000000000000000000000000000000000000000000000000",
    531     "30820124021d00baf696a68578f7dfdee7fa67c977c785ef32b233bae580c0bc"
    532         + "d5695e02820101008f7935d9b9aae9bfabed887acf4951b6f32ec59e3baf3718"
    533         + "e8eac4961f3efd3606e74351a9c4183339b809e7c2ae1c539ba7475b85d011ad"
    534         + "b8b47987754984695cac0e8f14b3360828a22ffa27110a3d62a993453409a0fe"
    535         + "696c4658f84bdd20819c3709a01057b195adcd00233dba5484b6291f9d648ef8"
    536         + "83448677979cec04b434a6ac2e75e9985de23db0292fc1118c9ffa9d8181e733"
    537         + "8db792b730d7b9e349592f68099872153915ea3d6b8b4653c633458f803b32a4"
    538         + "c2e0f27290256e4e3f8a3b0838a1c450e4e18c1a29a37ddf5ea143de4b66ff04"
    539         + "903ed5cf1623e158d487c608e97f211cd81dca23cb6e380765f822e342be484c"
    540         + "05763939601cd667",
    541     "3024021d00baf696a68578f7dfdee7fa67c977c785ef32b233bae580c0bcd5695e090380fe01",
    542     "303e021d01000000000000000000000000000000000000000000000000000000"
    543         + "00021dff450969597a870820211805983688387a10cd4dcc451a7f3f432a96a3",
    544     "3022021d0100000000000000000000000000000000000000000000000000000000020100",
    545     "3022021d0100000000000000000000000000000000000000000000000000000000020101",
    546     "3022021d01000000000000000000000000000000000000000000000000000000000201ff",
    547     "303e021d01000000000000000000000000000000000000000000000000000000"
    548         + "00021d00baf696a68578f7dfdee7fa67c977c785ef32b233bae580c0bcd5695d",
    549     "303e021d01000000000000000000000000000000000000000000000000000000"
    550         + "00021d00baf696a68578f7dfdee7fa67c977c785ef32b233bae580c0bcd5695e",
    551     "303e021d01000000000000000000000000000000000000000000000000000000"
    552         + "00021d0100000000000000000000000000000000000000000000000000000000",
    553     "30820124021d0100000000000000000000000000000000000000000000000000"
    554         + "00000002820101008f7935d9b9aae9bfabed887acf4951b6f32ec59e3baf3718"
    555         + "e8eac4961f3efd3606e74351a9c4183339b809e7c2ae1c539ba7475b85d011ad"
    556         + "b8b47987754984695cac0e8f14b3360828a22ffa27110a3d62a993453409a0fe"
    557         + "696c4658f84bdd20819c3709a01057b195adcd00233dba5484b6291f9d648ef8"
    558         + "83448677979cec04b434a6ac2e75e9985de23db0292fc1118c9ffa9d8181e733"
    559         + "8db792b730d7b9e349592f68099872153915ea3d6b8b4653c633458f803b32a4"
    560         + "c2e0f27290256e4e3f8a3b0838a1c450e4e18c1a29a37ddf5ea143de4b66ff04"
    561         + "903ed5cf1623e158d487c608e97f211cd81dca23cb6e380765f822e342be484c"
    562         + "05763939601cd667",
    563     "3024021d0100000000000000000000000000000000000000000000000000000000090380fe01",
    564     "3082012402820101008f7935d9b9aae9bfabed887acf4951b6f32ec59e3baf37"
    565         + "18e8eac4961f3efd3606e74351a9c4183339b809e7c2ae1c539ba7475b85d011"
    566         + "adb8b47987754984695cac0e8f14b3360828a22ffa27110a3d62a993453409a0"
    567         + "fe696c4658f84bdd20819c3709a01057b195adcd00233dba5484b6291f9d648e"
    568         + "f883448677979cec04b434a6ac2e75e9985de23db0292fc1118c9ffa9d8181e7"
    569         + "338db792b730d7b9e349592f68099872153915ea3d6b8b4653c633458f803b32"
    570         + "a4c2e0f27290256e4e3f8a3b0838a1c450e4e18c1a29a37ddf5ea143de4b66ff"
    571         + "04903ed5cf1623e158d487c608e97f211cd81dca23cb6e380765f822e342be48"
    572         + "4c05763939601cd667021dff450969597a870820211805983688387a10cd4dcc"
    573         + "451a7f3f432a96a3",
    574     "3082010802820101008f7935d9b9aae9bfabed887acf4951b6f32ec59e3baf37"
    575         + "18e8eac4961f3efd3606e74351a9c4183339b809e7c2ae1c539ba7475b85d011"
    576         + "adb8b47987754984695cac0e8f14b3360828a22ffa27110a3d62a993453409a0"
    577         + "fe696c4658f84bdd20819c3709a01057b195adcd00233dba5484b6291f9d648e"
    578         + "f883448677979cec04b434a6ac2e75e9985de23db0292fc1118c9ffa9d8181e7"
    579         + "338db792b730d7b9e349592f68099872153915ea3d6b8b4653c633458f803b32"
    580         + "a4c2e0f27290256e4e3f8a3b0838a1c450e4e18c1a29a37ddf5ea143de4b66ff"
    581         + "04903ed5cf1623e158d487c608e97f211cd81dca23cb6e380765f822e342be48"
    582         + "4c05763939601cd667020100",
    583     "3082010802820101008f7935d9b9aae9bfabed887acf4951b6f32ec59e3baf37"
    584         + "18e8eac4961f3efd3606e74351a9c4183339b809e7c2ae1c539ba7475b85d011"
    585         + "adb8b47987754984695cac0e8f14b3360828a22ffa27110a3d62a993453409a0"
    586         + "fe696c4658f84bdd20819c3709a01057b195adcd00233dba5484b6291f9d648e"
    587         + "f883448677979cec04b434a6ac2e75e9985de23db0292fc1118c9ffa9d8181e7"
    588         + "338db792b730d7b9e349592f68099872153915ea3d6b8b4653c633458f803b32"
    589         + "a4c2e0f27290256e4e3f8a3b0838a1c450e4e18c1a29a37ddf5ea143de4b66ff"
    590         + "04903ed5cf1623e158d487c608e97f211cd81dca23cb6e380765f822e342be48"
    591         + "4c05763939601cd667020101",
    592     "3082010802820101008f7935d9b9aae9bfabed887acf4951b6f32ec59e3baf37"
    593         + "18e8eac4961f3efd3606e74351a9c4183339b809e7c2ae1c539ba7475b85d011"
    594         + "adb8b47987754984695cac0e8f14b3360828a22ffa27110a3d62a993453409a0"
    595         + "fe696c4658f84bdd20819c3709a01057b195adcd00233dba5484b6291f9d648e"
    596         + "f883448677979cec04b434a6ac2e75e9985de23db0292fc1118c9ffa9d8181e7"
    597         + "338db792b730d7b9e349592f68099872153915ea3d6b8b4653c633458f803b32"
    598         + "a4c2e0f27290256e4e3f8a3b0838a1c450e4e18c1a29a37ddf5ea143de4b66ff"
    599         + "04903ed5cf1623e158d487c608e97f211cd81dca23cb6e380765f822e342be48"
    600         + "4c05763939601cd6670201ff",
    601     "3082012402820101008f7935d9b9aae9bfabed887acf4951b6f32ec59e3baf37"
    602         + "18e8eac4961f3efd3606e74351a9c4183339b809e7c2ae1c539ba7475b85d011"
    603         + "adb8b47987754984695cac0e8f14b3360828a22ffa27110a3d62a993453409a0"
    604         + "fe696c4658f84bdd20819c3709a01057b195adcd00233dba5484b6291f9d648e"
    605         + "f883448677979cec04b434a6ac2e75e9985de23db0292fc1118c9ffa9d8181e7"
    606         + "338db792b730d7b9e349592f68099872153915ea3d6b8b4653c633458f803b32"
    607         + "a4c2e0f27290256e4e3f8a3b0838a1c450e4e18c1a29a37ddf5ea143de4b66ff"
    608         + "04903ed5cf1623e158d487c608e97f211cd81dca23cb6e380765f822e342be48"
    609         + "4c05763939601cd667021d00baf696a68578f7dfdee7fa67c977c785ef32b233"
    610         + "bae580c0bcd5695d",
    611     "3082012402820101008f7935d9b9aae9bfabed887acf4951b6f32ec59e3baf37"
    612         + "18e8eac4961f3efd3606e74351a9c4183339b809e7c2ae1c539ba7475b85d011"
    613         + "adb8b47987754984695cac0e8f14b3360828a22ffa27110a3d62a993453409a0"
    614         + "fe696c4658f84bdd20819c3709a01057b195adcd00233dba5484b6291f9d648e"
    615         + "f883448677979cec04b434a6ac2e75e9985de23db0292fc1118c9ffa9d8181e7"
    616         + "338db792b730d7b9e349592f68099872153915ea3d6b8b4653c633458f803b32"
    617         + "a4c2e0f27290256e4e3f8a3b0838a1c450e4e18c1a29a37ddf5ea143de4b66ff"
    618         + "04903ed5cf1623e158d487c608e97f211cd81dca23cb6e380765f822e342be48"
    619         + "4c05763939601cd667021d00baf696a68578f7dfdee7fa67c977c785ef32b233"
    620         + "bae580c0bcd5695e",
    621     "3082012402820101008f7935d9b9aae9bfabed887acf4951b6f32ec59e3baf37"
    622         + "18e8eac4961f3efd3606e74351a9c4183339b809e7c2ae1c539ba7475b85d011"
    623         + "adb8b47987754984695cac0e8f14b3360828a22ffa27110a3d62a993453409a0"
    624         + "fe696c4658f84bdd20819c3709a01057b195adcd00233dba5484b6291f9d648e"
    625         + "f883448677979cec04b434a6ac2e75e9985de23db0292fc1118c9ffa9d8181e7"
    626         + "338db792b730d7b9e349592f68099872153915ea3d6b8b4653c633458f803b32"
    627         + "a4c2e0f27290256e4e3f8a3b0838a1c450e4e18c1a29a37ddf5ea143de4b66ff"
    628         + "04903ed5cf1623e158d487c608e97f211cd81dca23cb6e380765f822e342be48"
    629         + "4c05763939601cd667021d010000000000000000000000000000000000000000"
    630         + "0000000000000000",
    631     "3082020a02820101008f7935d9b9aae9bfabed887acf4951b6f32ec59e3baf37"
    632         + "18e8eac4961f3efd3606e74351a9c4183339b809e7c2ae1c539ba7475b85d011"
    633         + "adb8b47987754984695cac0e8f14b3360828a22ffa27110a3d62a993453409a0"
    634         + "fe696c4658f84bdd20819c3709a01057b195adcd00233dba5484b6291f9d648e"
    635         + "f883448677979cec04b434a6ac2e75e9985de23db0292fc1118c9ffa9d8181e7"
    636         + "338db792b730d7b9e349592f68099872153915ea3d6b8b4653c633458f803b32"
    637         + "a4c2e0f27290256e4e3f8a3b0838a1c450e4e18c1a29a37ddf5ea143de4b66ff"
    638         + "04903ed5cf1623e158d487c608e97f211cd81dca23cb6e380765f822e342be48"
    639         + "4c05763939601cd66702820101008f7935d9b9aae9bfabed887acf4951b6f32e"
    640         + "c59e3baf3718e8eac4961f3efd3606e74351a9c4183339b809e7c2ae1c539ba7"
    641         + "475b85d011adb8b47987754984695cac0e8f14b3360828a22ffa27110a3d62a9"
    642         + "93453409a0fe696c4658f84bdd20819c3709a01057b195adcd00233dba5484b6"
    643         + "291f9d648ef883448677979cec04b434a6ac2e75e9985de23db0292fc1118c9f"
    644         + "fa9d8181e7338db792b730d7b9e349592f68099872153915ea3d6b8b4653c633"
    645         + "458f803b32a4c2e0f27290256e4e3f8a3b0838a1c450e4e18c1a29a37ddf5ea1"
    646         + "43de4b66ff04903ed5cf1623e158d487c608e97f211cd81dca23cb6e380765f8"
    647         + "22e342be484c05763939601cd667",
    648     "3082010a02820101008f7935d9b9aae9bfabed887acf4951b6f32ec59e3baf37"
    649         + "18e8eac4961f3efd3606e74351a9c4183339b809e7c2ae1c539ba7475b85d011"
    650         + "adb8b47987754984695cac0e8f14b3360828a22ffa27110a3d62a993453409a0"
    651         + "fe696c4658f84bdd20819c3709a01057b195adcd00233dba5484b6291f9d648e"
    652         + "f883448677979cec04b434a6ac2e75e9985de23db0292fc1118c9ffa9d8181e7"
    653         + "338db792b730d7b9e349592f68099872153915ea3d6b8b4653c633458f803b32"
    654         + "a4c2e0f27290256e4e3f8a3b0838a1c450e4e18c1a29a37ddf5ea143de4b66ff"
    655         + "04903ed5cf1623e158d487c608e97f211cd81dca23cb6e380765f822e342be48"
    656         + "4c05763939601cd667090380fe01",
    657     "3024090380fe01021dff450969597a870820211805983688387a10cd4dcc451a7f3f432a96a3",
    658     "3008090380fe01020100",
    659     "3008090380fe01020101",
    660     "3008090380fe010201ff",
    661     "3024090380fe01021d00baf696a68578f7dfdee7fa67c977c785ef32b233bae580c0bcd5695d",
    662     "3024090380fe01021d00baf696a68578f7dfdee7fa67c977c785ef32b233bae580c0bcd5695e",
    663     "3024090380fe01021d0100000000000000000000000000000000000000000000000000000000",
    664     "3082010a090380fe0102820101008f7935d9b9aae9bfabed887acf4951b6f32e"
    665         + "c59e3baf3718e8eac4961f3efd3606e74351a9c4183339b809e7c2ae1c539ba7"
    666         + "475b85d011adb8b47987754984695cac0e8f14b3360828a22ffa27110a3d62a9"
    667         + "93453409a0fe696c4658f84bdd20819c3709a01057b195adcd00233dba5484b6"
    668         + "291f9d648ef883448677979cec04b434a6ac2e75e9985de23db0292fc1118c9f"
    669         + "fa9d8181e7338db792b730d7b9e349592f68099872153915ea3d6b8b4653c633"
    670         + "458f803b32a4c2e0f27290256e4e3f8a3b0838a1c450e4e18c1a29a37ddf5ea1"
    671         + "43de4b66ff04903ed5cf1623e158d487c608e97f211cd81dca23cb6e380765f8"
    672         + "22e342be484c05763939601cd667",
    673     "300a090380fe01090380fe01",
    674   };
    675 
    676   @SuppressWarnings("InsecureCryptoUsage")
    677   public void testVectors(
    678       String[] signatures,
    679       DSAPublicKeySpec key,
    680       String message,
    681       String algorithm,
    682       String signatureType,
    683       boolean isValidDER,
    684       boolean isValidBER)
    685       throws Exception {
    686     byte[] messageBytes = message.getBytes("UTF-8");
    687     Signature verifier = Signature.getInstance(algorithm);
    688     KeyFactory kf = KeyFactory.getInstance("DSA");
    689     PublicKey pub = kf.generatePublic(key);
    690     int errors = 0;
    691     for (String signature : signatures) {
    692       byte[] signatureBytes = TestUtil.hexToBytes(signature);
    693       verifier.initVerify(pub);
    694       verifier.update(messageBytes);
    695       boolean verified = false;
    696       try {
    697         verified = verifier.verify(signatureBytes);
    698       } catch (SignatureException ex) {
    699         // verify can throw SignatureExceptions if the signature is malformed.
    700         // We don't flag these cases and simply consider the signature as invalid.
    701         verified = false;
    702       } catch (Exception ex) {
    703         // Other exceptions indicate some internal error, e.g. careless ASN parsing.
    704         // We count these as errors.
    705         System.out.println(signatureType + ":" + signature + " throws:" + ex.toString());
    706         errors++;
    707         continue;
    708       }
    709       if (isValidDER && !verified) {
    710         System.out.println(signatureType + " was not verified:" + signature);
    711         errors++;
    712       } else if (!isValidBER && verified) {
    713         System.out.println(signatureType + " was verified:" + signature);
    714         errors++;
    715       }
    716     }
    717     assertEquals(0, errors);
    718   }
    719 
    720   public void testValidSignatures() throws Exception {
    721     testVectors(
    722         VALID_SIGNATURES, publicKey1, "Hello", "SHA224WithDSA", "Valid DSA signature", true, true);
    723   }
    724 
    725   public void testModifiedSignatures() throws Exception {
    726     testVectors(
    727         MODIFIED_SIGNATURES, publicKey1, "Hello", "SHA224WithDSA", "Modified DSA signature",
    728         false, true);
    729   }
    730 
    731   public void testInvalidSignatures() throws Exception {
    732     testVectors(
    733         INVALID_SIGNATURES, publicKey1, "Hello", "SHA224WithDSA", "Invalid DSA signature",
    734         false, false);
    735   }
    736 
    737   // Extract the integer r from a DSA signature.
    738   // This method implicitely assumes that the DSA signature is DER encoded.
    739   BigInteger extractR(byte[] signature) throws Exception {
    740     int lengthR = signature[3];
    741     return new BigInteger(Arrays.copyOfRange(signature, 4, 4 + lengthR));
    742   }
    743 
    744   BigInteger extractS(byte[] signature) throws Exception {
    745     int lengthR = signature[3];
    746     int startS = 4 + lengthR;
    747     int lengthS = signature[startS + 1];
    748     return new BigInteger(Arrays.copyOfRange(signature, startS + 2, startS + 2 + lengthS));
    749   }
    750 
    751   /** Extract the k that was used to sign the signature. Validates the k if check == true. */
    752   BigInteger extractK(byte[] signature, BigInteger h, DSAPrivateKey priv, boolean check)
    753       throws Exception {
    754     BigInteger x = priv.getX();
    755     BigInteger q = priv.getParams().getQ();
    756     BigInteger r = extractR(signature);
    757     BigInteger s = extractS(signature);
    758     BigInteger k = x.multiply(r).add(h).multiply(s.modInverse(q)).mod(q);
    759     if (check) {
    760       BigInteger p = priv.getParams().getP();
    761       BigInteger g = priv.getParams().getG();
    762       BigInteger r2 = g.modPow(k, p).mod(q);
    763       assertEquals(r.toString(), r2.toString());
    764     }
    765     return k;
    766   }
    767 
    768   /**
    769    * Providers that implement SHA1WithDSA but not at least SHA256WithDSA are outdated and should be
    770    * avoided even if DSA is currently not used in a project. Such providers promote using a weak
    771    * signature scheme. It can also "inspire" developers to use invalid schemes such as SHA1WithDSA
    772    * together with 2048-bit key. Such invalid use cases are often untested and can have serious
    773    * flaws. For example the SUN provider leaked the private keys with 3 to 5 signatures in such
    774    * instances.
    775    */
    776   public void testOutdatedProvider() throws Exception {
    777     try {
    778       Signature sig = Signature.getInstance("SHA1WithDSA");
    779       try {
    780         Signature.getInstance("SHA256WithDSA");
    781       } catch (NoSuchAlgorithmException ex) {
    782         fail("Provider " + sig.getProvider().getName() + " is outdated and should not be used.");
    783       }
    784     } catch (NoSuchAlgorithmException ex) {
    785       System.out.println("SHA1WithDSA is not supported");
    786     }
    787   }
    788 
    789   /**
    790    * This is just a test for basic functionality of DSA. The test generates a public and private
    791    * key, generates a signature, verifies it and prints the whole thing out. This test is useful
    792    * when an implementation is seriously broken.
    793    */
    794   @SlowTest(providers = {ProviderType.BOUNCY_CASTLE, ProviderType.SPONGY_CASTLE})
    795   @SuppressWarnings("InsecureCryptoUsage")
    796   public void testBasic() throws Exception {
    797     int keySize = 2048;
    798     String algorithm = "SHA256WithDSA";
    799     String hashAlgorithm = "SHA-256";
    800     String message = "Hello";
    801 
    802     byte[] messageBytes = message.getBytes("UTF-8");
    803     KeyPairGenerator generator = java.security.KeyPairGenerator.getInstance("DSA");
    804     generator.initialize(keySize);
    805     KeyPair keyPair = generator.generateKeyPair();
    806     DSAPublicKey pub = (DSAPublicKey) keyPair.getPublic();
    807     DSAPrivateKey priv = (DSAPrivateKey) keyPair.getPrivate();
    808     Signature signer = Signature.getInstance(algorithm);
    809     Signature verifier = Signature.getInstance(algorithm);
    810     signer.initSign(priv);
    811     signer.update(messageBytes);
    812     byte[] signature = signer.sign();
    813     verifier.initVerify(pub);
    814     verifier.update(messageBytes);
    815     assertTrue(verifier.verify(signature));
    816 
    817     // Extract some parameters.
    818     byte[] rawHash = MessageDigest.getInstance(hashAlgorithm).digest(messageBytes);
    819     DSAParams params = priv.getParams();
    820 
    821     // Print keys and signature, so that it can be used to generate new test vectors.
    822     System.out.println("Message:" + message);
    823     System.out.println("Hash:" + TestUtil.bytesToHex(rawHash));
    824     System.out.println("Params:");
    825     System.out.println("p:" + params.getP().toString());
    826     System.out.println("q:" + params.getQ().toString());
    827     System.out.println("g:" + params.getG().toString());
    828     System.out.println("Private key:");
    829     System.out.println("X:" + priv.getX().toString());
    830     System.out.println("encoded:" + TestUtil.bytesToHex(priv.getEncoded()));
    831     System.out.println("Public key:");
    832     System.out.println("Y:" + pub.getY().toString());
    833     System.out.println("encoded:" + TestUtil.bytesToHex(pub.getEncoded()));
    834     System.out.println("Signature:" + TestUtil.bytesToHex(signature));
    835     System.out.println("r:" + extractR(signature).toString());
    836     System.out.println("s:" + extractS(signature).toString());
    837   }
    838 
    839   @SuppressWarnings("InsecureCryptoUsage")
    840   public void testKeyGeneration(int keysize) throws Exception {
    841     KeyPairGenerator generator = KeyPairGenerator.getInstance("DSA");
    842     generator.initialize(keysize);
    843     KeyPair keyPair = generator.generateKeyPair();
    844     DSAPrivateKey priv = (DSAPrivateKey) keyPair.getPrivate();
    845     DSAParams params = priv.getParams();
    846     assertEquals(keysize, params.getP().bitLength());
    847     // The NIST standard does not fully specify the size of q that
    848     // must be used for a given key size. Hence there are differences.
    849     // For example if keysize = 2048, then OpenSSL uses 256 bit q's by default,
    850     // but the SUN provider uses 224 bits. Both are acceptable sizes.
    851     // The tests below simply asserts that the size of q does not decrease the
    852     // overall security of the DSA.
    853     int qsize = params.getQ().bitLength();
    854     switch (keysize) {
    855       case 1024:
    856         assertTrue("Invalid qsize for 1024 bit key:" + qsize, qsize >= 160);
    857         break;
    858       case 2048:
    859         assertTrue("Invalid qsize for 2048 bit key:" + qsize, qsize >= 224);
    860         break;
    861       case 3072:
    862         assertTrue("Invalid qsize for 3072 bit key:" + qsize, qsize >= 256);
    863         break;
    864       default:
    865         fail("Invalid key size:" + keysize);
    866     }
    867     // Check the length of the private key.
    868     // For example GPG4Browsers or the KJUR library derived from it use
    869     // q.bitCount() instead of q.bitLength() to determine the size of the private key
    870     // and hence would generate keys that are much too small.
    871     assertTrue(priv.getX().bitLength() >= qsize - 32);
    872   }
    873 
    874   /**
    875    * Tests the key generation for DSA.
    876    *
    877    * <p>Problems found:
    878    * <ul>
    879    * <li> CVE-2016-1000343 BouncyCastle before v.1.56 always generated DSA keys with
    880    * a 160-bit q.
    881    * </ul>
    882    */
    883   @SlowTest(providers = {ProviderType.BOUNCY_CASTLE, ProviderType.SPONGY_CASTLE})
    884   public void testKeyGenerationAll() throws Exception {
    885     testKeyGeneration(1024);
    886     testKeyGeneration(2048);
    887   }
    888 
    889   /**
    890    * Checks whether the one time key k in DSA is biased. For example the SUN provider fell for this
    891    * test until April 2016.
    892    */
    893   @SuppressWarnings("InsecureCryptoUsage")
    894   public void testDsaBias() throws Exception {
    895     // q is close to 2/3 * 2^160.
    896     BigInteger q = new BigInteger("974317976835659416858874959372334979171063697271");
    897     BigInteger p =
    898         new BigInteger(
    899             "1106803511314772711673172950296693567629309594518393175860816428"
    900                 + "6658764043763662129010863568011543182924292444458455864283745070"
    901                 + "9908516713302345161980412667892373845670780253725557376379049862"
    902                 + "4062950082444499320797079243439689601679418602390654466821968220"
    903                 + "32212146727497041502702331623782703855119908989712161");
    904     BigInteger g =
    905         new BigInteger(
    906             "1057342118316953575810387190942009018497979302261477972033090351"
    907                 + "7561815639397594841480480197745063606756857212792356354588585967"
    908                 + "3837265237205154744016475608524531648654928648461175919672511710"
    909                 + "4878976887505840764543501512668232945506391524642105449699321960"
    910                 + "32410302985148400531470153936516167243072120845392903");
    911     BigInteger x = new BigInteger("13706102843888006547723575730792302382646994436");
    912 
    913     KeyFactory kf = KeyFactory.getInstance("DSA");
    914     DSAPrivateKey priv = (DSAPrivateKey) kf.generatePrivate(new DSAPrivateKeySpec(x, p, q, g));
    915 
    916     // If we make TESTS tests with a fair coin then the probability that
    917     // either heads or tails appears less than MINCOUNT times is less than
    918     // 2^{-32}.
    919     // I.e. 2*sum(binomial(tests,i) for i in range(mincount))*2**32 < 2**tests
    920     // Therefore the test below is not expected to fail unless the generation
    921     // of the one time keys is indeed biased.
    922     final int tests = 1024;
    923     final int mincount = 410;
    924 
    925     String hashAlgorithm = "SHA";
    926     String message = "Hello";
    927     byte[] messageBytes = message.getBytes("UTF-8");
    928     byte[] digest = MessageDigest.getInstance(hashAlgorithm).digest(messageBytes);
    929     BigInteger h = new BigInteger(1, digest);
    930 
    931     final BigInteger qHalf = q.shiftRight(1);
    932     Signature signer = Signature.getInstance("SHA1WithDSA");
    933     signer.initSign(priv);
    934     int countLsb = 0; // count the number of k's with msb set
    935     int countMsb = 0; // count the number of k's with lsb set
    936     for (int i = 0; i < tests; i++) {
    937       signer.update(messageBytes);
    938       byte[] signature = signer.sign();
    939       BigInteger k = extractK(signature, h, priv, i < 10);
    940       if (k.testBit(0)) {
    941         countLsb++;
    942       }
    943       if (k.compareTo(qHalf) == 1) {
    944         countMsb++;
    945       }
    946     }
    947     if (countLsb < mincount || countLsb > tests - mincount) {
    948       fail("Bias detected in the least significant bit of k:" + countLsb);
    949     }
    950     if (countMsb < mincount || countMsb > tests - mincount) {
    951       fail("Bias detected in the most significant bit of k:" + countMsb);
    952     }
    953   }
    954 
    955   /**
    956    * Checks whether CVE-2016-0695 has been fixed. Before the April 2016 security update, the SUN
    957    * provider had a serious flaw that leaked the private key with about 3-5 signatures. In
    958    * particular, "Sha1WithDSA" always generated 160 bit k's independently of q. Unfortunately, it is
    959    * easily possible to use 2048 and 3072 bit DSA keys together with SHA1WithDSA. All a user has to
    960    * do is to use the algorithm name "DSA" instead of "SHA256WithDSA" rsp. "SHA224WithDSA".
    961    *
    962    * <p>An algorithm to extract the key from the signatures has been described for example in the
    963    * paper <a href="http://www.hpl.hp.com/techreports/1999/HPL-1999-90.pdf">Lattice Attacks on
    964    * Digital Signature Schemes</a> by N.A. Howgrave-Graham, N.P. Smart.
    965    *
    966    * <p>This bug is the same as US-CERT: VU # 940388: GnuPG generated ElGamal signatures that leaked
    967    * the private key.
    968    */
    969   @SlowTest(providers = {ProviderType.BOUNCY_CASTLE, ProviderType.SPONGY_CASTLE})
    970   @SuppressWarnings("InsecureCryptoUsage")
    971   public void testBiasSha1WithDSA() throws Exception {
    972     String hashAlgorithm = "SHA";
    973     String message = "Hello";
    974     byte[] messageBytes = message.getBytes("UTF-8");
    975     byte[] digest = MessageDigest.getInstance(hashAlgorithm).digest(messageBytes);
    976     BigInteger h = new BigInteger(1, digest);
    977 
    978     KeyPairGenerator generator = java.security.KeyPairGenerator.getInstance("DSA");
    979     generator.initialize(2048);
    980     KeyPair keyPair = generator.generateKeyPair();
    981     DSAPrivateKey priv = (DSAPrivateKey) keyPair.getPrivate();
    982     Signature signer = Signature.getInstance("DSA");
    983     try {
    984       // Private key and selected algorithm by signer do not match.
    985       // Hence throwing an exception at this point would be the reasonable.
    986       signer.initSign(priv);
    987       signer.update(messageBytes);
    988       byte[] signature = signer.sign();
    989       BigInteger q = priv.getParams().getQ();
    990       BigInteger k = extractK(signature, h, priv, true);
    991 
    992       // Now check if k is heavily biased.
    993       int lengthDiff = q.bitLength() - k.bitLength();
    994       if (lengthDiff > 32) {
    995         fail(
    996             "Severly biased DSA signature:"
    997                 + " len(q)="
    998                 + q.bitLength()
    999                 + " len(k)="
   1000                 + k.bitLength());
   1001       }
   1002     } catch (GeneralSecurityException ex) {
   1003       // The key is invalid, hence getting here is reasonable.
   1004       return;
   1005     }
   1006   }
   1007 
   1008   /**
   1009    * This test checks for potential of a timing attack. The test generates a number of signatures,
   1010    * selects a fraction of them with a small timing and then compares the values k for the selected
   1011    * signatures with a normal distribution. The test fails if these ks are much smaller than
   1012    * expected. An implementation flaw that can lead to a test failure is to compute the signature
   1013    * with a modular exponentiation with a runtime that depend on the length of the exponent.
   1014    *
   1015    * <p>A failing test simply means that the timing can be used to get information about k. Further
   1016    * analysis is necessary to determine if the bias is exploitable and how many timings are
   1017    * necessary for an attack. A passing test does not mean that the implementation is secure against
   1018    * timing attacks. The test only catches relatively big timing differences. It requires high
   1019    * confidence to fail. Noise on the test machine can prevent that a relation between timing and k
   1020    * can be detected.
   1021    *
   1022    * <p>Claims of what is exploitable: http://www.hpl.hp.com/techreports/1999/HPL-1999-90.pdf 30
   1023    * signatures are sufficient to find the private key if the attacker knows 8 bits of each k.
   1024    * http://eprint.iacr.org/2004/277.pdf 27 signatures are sufficient if 8 bits of each k is known.
   1025    * Our own old experiments (using 1GB memory on a Pentium-4? CPU): 2^11 signatures are sufficient
   1026    * with a 3 bit leakage. 2^15 signatures are sufficient with a 2 bit leakage. 2^24 signatures are
   1027    * sufficient with a 1 bit leakage. Estimate for biased generation in the NIST standard: e.g. 2^22
   1028    * signatures, 2^40 memory, 2^64 time
   1029    *
   1030    * <p><b>Sample output for the SUN provider:</b> <code>
   1031    * count:50000 cutoff:4629300 relative average:0.9992225872624547 sigmas:0.3010906585642381
   1032    * count:25000 cutoff:733961 relative average:0.976146066585879 sigmas:6.532668708070148
   1033    * count:12500 cutoff:688305 relative average:0.9070352192339134 sigmas:18.00255238454385
   1034    * count:6251 cutoff:673971 relative average:0.7747148791368986 sigmas:30.850903417893825
   1035    * count:3125 cutoff:667045 relative average:0.5901994097874541 sigmas:39.67877152897901
   1036    * count:1563 cutoff:662088 relative average:0.4060286694971057 sigmas:40.67294313795137
   1037    * count:782 cutoff:657921 relative average:0.2577955312387898 sigmas:35.94906247333319
   1038    * count:391 cutoff:653608 relative average:0.1453438859272699 sigmas:29.271192100879457
   1039    * count:196 cutoff:649280 relative average:0.08035497211567771 sigmas:22.300206785132406
   1040    * count:98 cutoff:645122 relative average:0.05063589092661368 sigmas:16.27820353139225
   1041    * count:49 cutoff:641582 relative average:0.018255560447883384 sigmas:11.903018745467488
   1042    * count:25 cutoff:638235 relative average:0.009082660721102722 sigmas:8.581595888660086
   1043    * count:13 cutoff:633975 relative average:0.0067892346039088326 sigmas:6.20259924188633
   1044    * </code>
   1045    *
   1046    * <p><b>What this shows:</b> The first line uses all 50'000 signatures. The average k of these
   1047    * signatures is close to the expected value q/2. Being more selective gives us signatures with a
   1048    * more biased k. For example, the 196 signatures with the fastest timing have about a 3-bit bias.
   1049    * From this we expect that 2^19 signatures and timings are sufficient to find the private key.
   1050    *
   1051    * <p>A list of problems caught by this test:
   1052    * <ul>
   1053    * <li> CVE-2016-5548 OpenJDK8's DSA is vulnerable to timing attacks.
   1054    * <li> CVE-2016-1000341 BouncyCastle before v 1.56 is vulnernerable to timing attacks.
   1055    * </ul>
   1056    */
   1057   @SlowTest(providers = {ProviderType.BOUNCY_CASTLE, ProviderType.OPENJDK,
   1058     ProviderType.SPONGY_CASTLE})
   1059   @SuppressWarnings("InsecureCryptoUsage")
   1060   public void testTiming() throws Exception {
   1061     // BEGIN Android-removed: Android doesn't support JMX
   1062     /*
   1063     ThreadMXBean bean = ManagementFactory.getThreadMXBean();
   1064     if (!bean.isCurrentThreadCpuTimeSupported()) {
   1065       System.out.println("getCurrentThreadCpuTime is not supported. Skipping");
   1066       return;
   1067     }
   1068     String hashAlgorithm = "SHA-1";
   1069     String message = "Hello";
   1070     byte[] messageBytes = message.getBytes("UTF-8");
   1071     byte[] digest = MessageDigest.getInstance(hashAlgorithm).digest(messageBytes);
   1072     BigInteger h = new BigInteger(1, digest);
   1073     KeyPairGenerator generator = java.security.KeyPairGenerator.getInstance("DSA");
   1074     generator.initialize(1024);
   1075     KeyPair keyPair = generator.generateKeyPair();
   1076     DSAPrivateKey priv = (DSAPrivateKey) keyPair.getPrivate();
   1077     Signature signer = Signature.getInstance("SHA1WITHDSA");
   1078     signer.initSign(priv);
   1079     // The timings below are quite noisy. Thus we need a large number of samples.
   1080     int samples = 50000;
   1081     long[] timing = new long[samples];
   1082     BigInteger[] k = new BigInteger[samples];
   1083     for (int i = 0; i < samples; i++) {
   1084       long start = bean.getCurrentThreadCpuTime();
   1085       signer.update(messageBytes);
   1086       byte[] signature = signer.sign();
   1087       timing[i] = bean.getCurrentThreadCpuTime() - start;
   1088       k[i] = extractK(signature, h, priv, false);
   1089     }
   1090     long[] sorted = Arrays.copyOf(timing, timing.length);
   1091     Arrays.sort(sorted);
   1092     // Here we are only interested in roughly the 8 most significant bits of the ks.
   1093     // Hence, using double is sufficiently precise.
   1094     double q = priv.getParams().getQ().doubleValue();
   1095     double expectedAverage = q / 2;
   1096     double maxSigmas = 0;
   1097     System.out.println("testTiming: SHA1WITHDSA");
   1098     for (int idx = samples - 1; idx > 10; idx /= 2) {
   1099       long cutoff = sorted[idx];
   1100       int count = 0;
   1101       double total = 0;
   1102       for (int i = 0; i < samples; i++) {
   1103         if (timing[i] <= cutoff) {
   1104           total += k[i].doubleValue();
   1105           count += 1;
   1106         }
   1107       }
   1108       double expectedStdDev = q / Math.sqrt(12 * count);
   1109       double average = total / count;
   1110       // Number of standard deviations that the average is away from
   1111       // the expected value:
   1112       double sigmas = (expectedAverage - average) / expectedStdDev;
   1113       if (sigmas > maxSigmas) {
   1114         maxSigmas = sigmas;
   1115       }
   1116       System.out.println(
   1117           "count:"
   1118               + count
   1119               + " cutoff:"
   1120               + cutoff
   1121               + " relative average:"
   1122               + (average / expectedAverage)
   1123               + " sigmas:"
   1124               + sigmas);
   1125     }
   1126     // Checks if the signatures with a small timing have a biased k.
   1127     // We use 7 standard deviations, so that the probability of a false positive is smaller
   1128     // than 10^{-10}.
   1129     if (maxSigmas >= 7) {
   1130       fail("Signatures with short timing have a biased k");
   1131     }
   1132     */
   1133     // END Android-removed: Android doesn't support JMX
   1134   }
   1135 
   1136   /**
   1137    * DSA does not allow encryption. This test verifies that a provider does not implement an ad hoc
   1138    * scheme that attempts to turn DSA into a public key encryption scheme.
   1139    */
   1140   @SuppressWarnings("InsecureCryptoUsage")
   1141   public void testEncryptionWithDsa() throws Exception {
   1142     try {
   1143       Cipher cipher = Cipher.getInstance("DSA");
   1144       fail("DSA must not be used as a cipher:" + cipher.getProvider().toString());
   1145     } catch (NoSuchAlgorithmException ex) {
   1146       // This is expected
   1147     }
   1148   }
   1149 }
   1150