The Insecurity of the Digital Signature Algorithm with Partially Known Nonces View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2002-06

AUTHORS

Nguyen, Shparlinski

ABSTRACT

We present a polynomial-time algorithm that provably recovers the signer's secret DSA key when a few consecutive bits of the random nonces k (used at each signature generation) are known for a number of DSA signatures at most linear in log q (q denoting as usual the small prime of DSA), under a reasonable assumption on the hash function used in DSA. For most significant or least significant bits, the number of required bits is about log1/2 q , but can be decreased to log log q with a running time qO(1/log log q) subexponential in log q , and even further to two in polynomial time if one assumes access to ideal lattice basis reduction, namely an oracle for the lattice closest vector problem for the infinity norm. For arbitrary consecutive bits, the attack requires twice as many bits. All previously known results were only heuristic, including those of Howgrave-Graham and Smart who recently introduced that topic. Our attack is based on a connection with the hidden number problem (HNP) introduced at Crypto '96 by Boneh and Venkatesan in order to study the bit-security of the Diffie—Hellman key exchange. The HNP consists, given a prime number q , of recovering a number α ∈ Fq such that for many known random t ∈ Fq a certain approximation of t α is known. To handle the DSA case, we extend Boneh and Venkatesan's results on the HNP to the case where t has not necessarily perfectly uniform distribution, and establish uniformity statements on the DSA signatures, using exponential sum techniques. The efficiency of our attack has been validated experimentally, and illustrates once again the fact that one should be very cautious with the pseudo-random generation of the nonce within DSA. More... »

PAGES

151-176

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00145-002-0021-3

DOI

http://dx.doi.org/10.1007/s00145-002-0021-3

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1032609859


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "name": [
            "D\u00e9partement d'Informatique, \u00c9cole Normale Sup{\u00e9}rieure,   45 rue d'Ulm, 75230 Paris Cedex 05, France   pnguyen@ens.fr    http://www.di.ens.fr/~pnguyen, FR"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Nguyen", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Macquarie University", 
          "id": "https://www.grid.ac/institutes/grid.1004.5", 
          "name": [
            "Department of Computing, Macquarie University,   Sydney, NSW 2109, Australia   igor@comp.mq.edu.au   http://www.comp.mq.edu.au/~igor/, AU"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Shparlinski", 
        "type": "Person"
      }
    ], 
    "datePublished": "2002-06", 
    "datePublishedReg": "2002-06-01", 
    "description": "We present a polynomial-time algorithm that provably recovers the signer's secret DSA key when a few consecutive bits of the random nonces k (used at each signature generation) are known for a number of DSA signatures at most linear in log q (q denoting as usual the small prime of DSA), under a reasonable assumption on the hash function used in DSA. For most significant or least significant bits, the number of required bits is about log1/2 q , but can be decreased to log log q with a running time qO(1/log log q) subexponential in log q , and even further to two in polynomial time if one assumes access to ideal lattice basis reduction, namely an oracle for the lattice closest vector problem for the infinity norm. For arbitrary consecutive bits, the attack requires twice as many bits. All previously known results were only heuristic, including those of Howgrave-Graham and Smart who recently introduced that topic. Our attack is based on a connection with the hidden number problem (HNP) introduced at Crypto '96 by Boneh and Venkatesan in order to study the bit-security of the Diffie\u2014Hellman key exchange. The HNP consists, given a prime number q , of recovering a number \u03b1 \u2208 Fq such that for many known random t \u2208 Fq a certain approximation of t \u03b1 is known. To handle the DSA case, we extend Boneh and Venkatesan's results on the HNP to the case where t has not necessarily perfectly uniform distribution, and establish uniformity statements on the DSA signatures, using exponential sum techniques. The efficiency of our attack has been validated experimentally, and illustrates once again the fact that one should be very cautious with the pseudo-random generation of the nonce within DSA.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s00145-002-0021-3", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1136278", 
        "issn": [
          "0933-2790", 
          "1432-1378"
        ], 
        "name": "Journal of Cryptology", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "3", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "15"
      }
    ], 
    "name": "The Insecurity of the Digital Signature Algorithm with Partially Known Nonces", 
    "pagination": "151-176", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "9b59dff17fb0e9c58c0f8752bee9383784cbfe329ec62cf4ebfa68d0e6d09a02"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00145-002-0021-3"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1032609859"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00145-002-0021-3", 
      "https://app.dimensions.ai/details/publication/pub.1032609859"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-10T16:42", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8669_00000513.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007%2Fs00145-002-0021-3"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s00145-002-0021-3'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s00145-002-0021-3'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00145-002-0021-3'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00145-002-0021-3'


 

This table displays all metadata directly associated to this object as RDF triples.

66 TRIPLES      20 PREDICATES      27 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00145-002-0021-3 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nd3edf5b9007a498b98178e5f06396d53
4 schema:datePublished 2002-06
5 schema:datePublishedReg 2002-06-01
6 schema:description We present a polynomial-time algorithm that provably recovers the signer's secret DSA key when a few consecutive bits of the random nonces k (used at each signature generation) are known for a number of DSA signatures at most linear in log q (q denoting as usual the small prime of DSA), under a reasonable assumption on the hash function used in DSA. For most significant or least significant bits, the number of required bits is about log1/2 q , but can be decreased to log log q with a running time qO(1/log log q) subexponential in log q , and even further to two in polynomial time if one assumes access to ideal lattice basis reduction, namely an oracle for the lattice closest vector problem for the infinity norm. For arbitrary consecutive bits, the attack requires twice as many bits. All previously known results were only heuristic, including those of Howgrave-Graham and Smart who recently introduced that topic. Our attack is based on a connection with the hidden number problem (HNP) introduced at Crypto '96 by Boneh and Venkatesan in order to study the bit-security of the Diffie—Hellman key exchange. The HNP consists, given a prime number q , of recovering a number α ∈ Fq such that for many known random t ∈ Fq a certain approximation of t α is known. To handle the DSA case, we extend Boneh and Venkatesan's results on the HNP to the case where t has not necessarily perfectly uniform distribution, and establish uniformity statements on the DSA signatures, using exponential sum techniques. The efficiency of our attack has been validated experimentally, and illustrates once again the fact that one should be very cautious with the pseudo-random generation of the nonce within DSA.
7 schema:genre research_article
8 schema:inLanguage en
9 schema:isAccessibleForFree false
10 schema:isPartOf N741a7fd46f3b411d8d8ac135072dbe57
11 N8fae901e686947e3971313256653da5b
12 sg:journal.1136278
13 schema:name The Insecurity of the Digital Signature Algorithm with Partially Known Nonces
14 schema:pagination 151-176
15 schema:productId N412e27d304a642f7a81790a9c0517760
16 N58635035d08b4a2ebe46a6a47318f751
17 N8382577bc0a844ed8ff7f59da5878d4e
18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032609859
19 https://doi.org/10.1007/s00145-002-0021-3
20 schema:sdDatePublished 2019-04-10T16:42
21 schema:sdLicense https://scigraph.springernature.com/explorer/license/
22 schema:sdPublisher Nc5d291370d754e399e811e73c4aae5ef
23 schema:url http://link.springer.com/10.1007%2Fs00145-002-0021-3
24 sgo:license sg:explorer/license/
25 sgo:sdDataset articles
26 rdf:type schema:ScholarlyArticle
27 N3a2e3978d8884792b57296a2b4d30580 rdf:first Ncdf74e2360234c88a98eab69b395955f
28 rdf:rest rdf:nil
29 N412e27d304a642f7a81790a9c0517760 schema:name doi
30 schema:value 10.1007/s00145-002-0021-3
31 rdf:type schema:PropertyValue
32 N58635035d08b4a2ebe46a6a47318f751 schema:name readcube_id
33 schema:value 9b59dff17fb0e9c58c0f8752bee9383784cbfe329ec62cf4ebfa68d0e6d09a02
34 rdf:type schema:PropertyValue
35 N741a7fd46f3b411d8d8ac135072dbe57 schema:volumeNumber 15
36 rdf:type schema:PublicationVolume
37 N79c64dbc49ca4f8a8671a8111b8d0a6b schema:affiliation Nc77143e7975340f6bed35cf53d2fedc1
38 schema:familyName Nguyen
39 rdf:type schema:Person
40 N8382577bc0a844ed8ff7f59da5878d4e schema:name dimensions_id
41 schema:value pub.1032609859
42 rdf:type schema:PropertyValue
43 N8fae901e686947e3971313256653da5b schema:issueNumber 3
44 rdf:type schema:PublicationIssue
45 Nc5d291370d754e399e811e73c4aae5ef schema:name Springer Nature - SN SciGraph project
46 rdf:type schema:Organization
47 Nc77143e7975340f6bed35cf53d2fedc1 schema:name Département d'Informatique, École Normale Sup{é}rieure, 45 rue d'Ulm, 75230 Paris Cedex 05, France pnguyen@ens.fr http://www.di.ens.fr/~pnguyen, FR
48 rdf:type schema:Organization
49 Ncdf74e2360234c88a98eab69b395955f schema:affiliation https://www.grid.ac/institutes/grid.1004.5
50 schema:familyName Shparlinski
51 rdf:type schema:Person
52 Nd3edf5b9007a498b98178e5f06396d53 rdf:first N79c64dbc49ca4f8a8671a8111b8d0a6b
53 rdf:rest N3a2e3978d8884792b57296a2b4d30580
54 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
55 schema:name Information and Computing Sciences
56 rdf:type schema:DefinedTerm
57 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
58 schema:name Computation Theory and Mathematics
59 rdf:type schema:DefinedTerm
60 sg:journal.1136278 schema:issn 0933-2790
61 1432-1378
62 schema:name Journal of Cryptology
63 rdf:type schema:Periodical
64 https://www.grid.ac/institutes/grid.1004.5 schema:alternateName Macquarie University
65 schema:name Department of Computing, Macquarie University, Sydney, NSW 2109, Australia igor@comp.mq.edu.au http://www.comp.mq.edu.au/~igor/, AU
66 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...