Relaxing Full-Codebook Security: A Refined Analysis of Key-Length Extension Schemes View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2015-08-12

AUTHORS

Peter Gaži , Jooyoung Lee , Yannick Seurin , John Steinberger , Stefano Tessaro

ABSTRACT

We revisit the security (as a pseudorandom permutation) of cascading-based constructions for block-cipher key-length extension. Previous works typically considered the extreme case where the adversary is given the entire codebook of the construction, the only complexity measure being the number qe\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$q_e$$\end{document} of queries to the underlying ideal block cipher, representing adversary’s secret-key-independent computation. Here, we initiate a systematic study of the more natural case of an adversary restricted to adaptively learning a number qc\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$q_c$$\end{document} of plaintext/ciphertext pairs that is less than the entire codebook. For any such qc\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$q_c$$\end{document}, we aim to determine the highest number of block-cipher queries qe\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$q_e$$\end{document} the adversary can issue without being able to successfully distinguish the construction (under a secret key) from a random permutation.More concretely, we show the following results for key-length extension schemes using a block cipher with n-bit blocks and κ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\kappa $$\end{document}-bit keys:Plain cascades of length ℓ=2r+1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell =2r+1$$\end{document} are secure whenever qcqer≪2r(κ+n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$q_cq_e^r \ll 2^{r(\kappa +n)}$$\end{document}, qc≪2κ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$q_c \ll 2^\kappa $$\end{document} and qe≪22κ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$q_e \ll 2^{2\kappa }$$\end{document}. The bound for r=1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r = 1$$\end{document} also applies to two-key triple encryption (as used within Triple DES).The r-round XOR-cascade is secure as long as qcqer≪2r(κ+n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$q_cq_e^r \ll 2^{r(\kappa +n)}$$\end{document}, matching an attack by Gaži (CRYPTO 2013).We fully characterize the security of Gaži and Tessaro’s two-call 2XOR\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathsf {2XOR}$$\end{document} construction (EUROCRYPT 2012) for all values of qc\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$q_c$$\end{document}, and note that the addition of a third whitening step strictly increases security for 2n/4≤qc≤23/4n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{n/4} \le q_c \le 2^{3/4n}$$\end{document}. We also propose a variant of this construction without re-keying and achieving comparable security levels. More... »

PAGES

319-341

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-662-48116-5_16

DOI

http://dx.doi.org/10.1007/978-3-662-48116-5_16

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0804", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Data Format", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "IST Austria, Klosterneuburg, Austria", 
          "id": "http://www.grid.ac/institutes/grid.33565.36", 
          "name": [
            "IST Austria, Klosterneuburg, Austria"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ga\u017ei", 
        "givenName": "Peter", 
        "id": "sg:person.012620015221.67", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012620015221.67"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Sejong University, Seoul, Korea", 
          "id": "http://www.grid.ac/institutes/grid.263333.4", 
          "name": [
            "Sejong University, Seoul, Korea"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lee", 
        "givenName": "Jooyoung", 
        "id": "sg:person.011041256670.23", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011041256670.23"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "ANSSI, Paris, France", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "ANSSI, Paris, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Seurin", 
        "givenName": "Yannick", 
        "id": "sg:person.011724731171.01", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011724731171.01"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Tsinghua University, Beijing, People\u2019s Republic of China", 
          "id": "http://www.grid.ac/institutes/grid.12527.33", 
          "name": [
            "Tsinghua University, Beijing, People\u2019s Republic of China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Steinberger", 
        "givenName": "John", 
        "id": "sg:person.010755664661.02", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010755664661.02"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "UC Santa Barbara, Santa Barbara, USA", 
          "id": "http://www.grid.ac/institutes/grid.133342.4", 
          "name": [
            "UC Santa Barbara, Santa Barbara, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Tessaro", 
        "givenName": "Stefano", 
        "id": "sg:person.014325641465.55", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014325641465.55"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2015-08-12", 
    "datePublishedReg": "2015-08-12", 
    "description": "We revisit the security (as a pseudorandom permutation) of cascading-based constructions for block-cipher key-length extension. Previous works typically considered the extreme case where the adversary is given the entire codebook of the construction, the only complexity measure being the number qe\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$q_e$$\\end{document} of queries to the underlying ideal block cipher, representing adversary\u2019s secret-key-independent computation. Here, we initiate a systematic study of the more natural case of an adversary restricted to adaptively learning a number qc\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$q_c$$\\end{document} of plaintext/ciphertext pairs that is less than the entire codebook. For any such qc\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$q_c$$\\end{document}, we aim to determine the highest number of block-cipher queries qe\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$q_e$$\\end{document} the adversary can issue without being able to successfully distinguish the construction (under a secret key) from a random permutation.More concretely, we show the following results for key-length extension schemes using a block cipher with n-bit blocks and \u03ba\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\kappa $$\\end{document}-bit keys:Plain cascades of length \u2113=2r+1\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\ell =2r+1$$\\end{document} are secure whenever qcqer\u226a2r(\u03ba+n)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$q_cq_e^r \\ll 2^{r(\\kappa +n)}$$\\end{document}, qc\u226a2\u03ba\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$q_c \\ll 2^\\kappa $$\\end{document} and qe\u226a22\u03ba\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$q_e \\ll 2^{2\\kappa }$$\\end{document}. The bound for r=1\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$r = 1$$\\end{document} also applies to two-key triple encryption (as used within Triple DES).The r-round XOR-cascade is secure as long as qcqer\u226a2r(\u03ba+n)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$q_cq_e^r \\ll 2^{r(\\kappa +n)}$$\\end{document}, matching an attack by Ga\u017ei (CRYPTO\u00a02013).We fully characterize the security of Ga\u017ei and Tessaro\u2019s two-call 2XOR\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\mathsf {2XOR}$$\\end{document} construction (EUROCRYPT 2012) for all values of qc\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$q_c$$\\end{document}, and note that the addition of a third whitening step strictly increases security for 2n/4\u2264qc\u226423/4n\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$2^{n/4} \\le q_c \\le 2^{3/4n}$$\\end{document}. We also propose a variant of this construction without re-keying and achieving comparable security levels.", 
    "editor": [
      {
        "familyName": "Leander", 
        "givenName": "Gregor", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-662-48116-5_16", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-662-48115-8", 
        "978-3-662-48116-5"
      ], 
      "name": "Fast Software Encryption", 
      "type": "Book"
    }, 
    "keywords": [
      "entire codebook", 
      "block cipher", 
      "two-key triple encryption", 
      "ideal block cipher", 
      "plaintext/ciphertext pairs", 
      "extension scheme", 
      "bit keys", 
      "triple encryption", 
      "comparable security levels", 
      "security level", 
      "security", 
      "adversary", 
      "complexity measures", 
      "queries", 
      "cipher", 
      "independent computations", 
      "ciphertext pairs", 
      "n-bit blocks", 
      "previous work", 
      "codebook", 
      "random permutation", 
      "scheme", 
      "encryption", 
      "computation", 
      "attacks", 
      "Ga\u017ei", 
      "Tessaro", 
      "construction", 
      "extension", 
      "number", 
      "permutations", 
      "key", 
      "refined analysis", 
      "work", 
      "extreme cases", 
      "results", 
      "block", 
      "step", 
      "cases", 
      "measures", 
      "natural cases", 
      "pairs", 
      "higher number", 
      "addition", 
      "variants", 
      "analysis", 
      "systematic study", 
      "study", 
      "length", 
      "values", 
      "levels", 
      "cascade"
    ], 
    "name": "Relaxing Full-Codebook Security: A Refined Analysis of Key-Length Extension Schemes", 
    "pagination": "319-341", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1011022590"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-662-48116-5_16"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-662-48116-5_16", 
      "https://app.dimensions.ai/details/publication/pub.1011022590"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-11-24T21:13", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221124/entities/gbq_results/chapter/chapter_187.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-662-48116-5_16"
  }
]
 

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/978-3-662-48116-5_16'

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/978-3-662-48116-5_16'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-48116-5_16'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-48116-5_16'


 

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

151 TRIPLES      22 PREDICATES      76 URIs      69 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-662-48116-5_16 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author Nef6342bee85040b8a72dc62214cb27eb
4 schema:datePublished 2015-08-12
5 schema:datePublishedReg 2015-08-12
6 schema:description We revisit the security (as a pseudorandom permutation) of cascading-based constructions for block-cipher key-length extension. Previous works typically considered the extreme case where the adversary is given the entire codebook of the construction, the only complexity measure being the number qe\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$q_e$$\end{document} of queries to the underlying ideal block cipher, representing adversary’s secret-key-independent computation. Here, we initiate a systematic study of the more natural case of an adversary restricted to adaptively learning a number qc\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$q_c$$\end{document} of plaintext/ciphertext pairs that is less than the entire codebook. For any such qc\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$q_c$$\end{document}, we aim to determine the highest number of block-cipher queries qe\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$q_e$$\end{document} the adversary can issue without being able to successfully distinguish the construction (under a secret key) from a random permutation.More concretely, we show the following results for key-length extension schemes using a block cipher with n-bit blocks and κ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\kappa $$\end{document}-bit keys:Plain cascades of length ℓ=2r+1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell =2r+1$$\end{document} are secure whenever qcqer≪2r(κ+n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$q_cq_e^r \ll 2^{r(\kappa +n)}$$\end{document}, qc≪2κ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$q_c \ll 2^\kappa $$\end{document} and qe≪22κ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$q_e \ll 2^{2\kappa }$$\end{document}. The bound for r=1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r = 1$$\end{document} also applies to two-key triple encryption (as used within Triple DES).The r-round XOR-cascade is secure as long as qcqer≪2r(κ+n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$q_cq_e^r \ll 2^{r(\kappa +n)}$$\end{document}, matching an attack by Gaži (CRYPTO 2013).We fully characterize the security of Gaži and Tessaro’s two-call 2XOR\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathsf {2XOR}$$\end{document} construction (EUROCRYPT 2012) for all values of qc\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$q_c$$\end{document}, and note that the addition of a third whitening step strictly increases security for 2n/4≤qc≤23/4n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{n/4} \le q_c \le 2^{3/4n}$$\end{document}. We also propose a variant of this construction without re-keying and achieving comparable security levels.
7 schema:editor N682377e3049b4384ae10eccc792097f8
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf N1c4f2bd23e0646d48d3eb8a167112c34
11 schema:keywords Gaži
12 Tessaro
13 addition
14 adversary
15 analysis
16 attacks
17 bit keys
18 block
19 block cipher
20 cascade
21 cases
22 cipher
23 ciphertext pairs
24 codebook
25 comparable security levels
26 complexity measures
27 computation
28 construction
29 encryption
30 entire codebook
31 extension
32 extension scheme
33 extreme cases
34 higher number
35 ideal block cipher
36 independent computations
37 key
38 length
39 levels
40 measures
41 n-bit blocks
42 natural cases
43 number
44 pairs
45 permutations
46 plaintext/ciphertext pairs
47 previous work
48 queries
49 random permutation
50 refined analysis
51 results
52 scheme
53 security
54 security level
55 step
56 study
57 systematic study
58 triple encryption
59 two-key triple encryption
60 values
61 variants
62 work
63 schema:name Relaxing Full-Codebook Security: A Refined Analysis of Key-Length Extension Schemes
64 schema:pagination 319-341
65 schema:productId N2a6c973ab07d4a1b845c09a144566c00
66 N3015598df66d4f37a58098f167173ec8
67 schema:publisher N20da7196d2b64383a04ddf7f4885dc9e
68 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011022590
69 https://doi.org/10.1007/978-3-662-48116-5_16
70 schema:sdDatePublished 2022-11-24T21:13
71 schema:sdLicense https://scigraph.springernature.com/explorer/license/
72 schema:sdPublisher N1823780a41074f6f8fc1252e681f922f
73 schema:url https://doi.org/10.1007/978-3-662-48116-5_16
74 sgo:license sg:explorer/license/
75 sgo:sdDataset chapters
76 rdf:type schema:Chapter
77 N12db570544fa4b14b8e70bf01fa4893a rdf:first sg:person.011724731171.01
78 rdf:rest Nd3b6cebe15734306bb519757dd00a2d9
79 N1823780a41074f6f8fc1252e681f922f schema:name Springer Nature - SN SciGraph project
80 rdf:type schema:Organization
81 N1c4f2bd23e0646d48d3eb8a167112c34 schema:isbn 978-3-662-48115-8
82 978-3-662-48116-5
83 schema:name Fast Software Encryption
84 rdf:type schema:Book
85 N20da7196d2b64383a04ddf7f4885dc9e schema:name Springer Nature
86 rdf:type schema:Organisation
87 N2a6c973ab07d4a1b845c09a144566c00 schema:name doi
88 schema:value 10.1007/978-3-662-48116-5_16
89 rdf:type schema:PropertyValue
90 N3015598df66d4f37a58098f167173ec8 schema:name dimensions_id
91 schema:value pub.1011022590
92 rdf:type schema:PropertyValue
93 N640c8c72a92a4363a6d5c50c4e1b530e rdf:first sg:person.014325641465.55
94 rdf:rest rdf:nil
95 N682377e3049b4384ae10eccc792097f8 rdf:first N6aa920a77a044c5cbe857d94069e83de
96 rdf:rest rdf:nil
97 N6aa920a77a044c5cbe857d94069e83de schema:familyName Leander
98 schema:givenName Gregor
99 rdf:type schema:Person
100 Nbc639e9c584142039e02149c9b09f83a rdf:first sg:person.011041256670.23
101 rdf:rest N12db570544fa4b14b8e70bf01fa4893a
102 Nd3b6cebe15734306bb519757dd00a2d9 rdf:first sg:person.010755664661.02
103 rdf:rest N640c8c72a92a4363a6d5c50c4e1b530e
104 Nef6342bee85040b8a72dc62214cb27eb rdf:first sg:person.012620015221.67
105 rdf:rest Nbc639e9c584142039e02149c9b09f83a
106 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
107 schema:name Information and Computing Sciences
108 rdf:type schema:DefinedTerm
109 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
110 schema:name Data Format
111 rdf:type schema:DefinedTerm
112 sg:person.010755664661.02 schema:affiliation grid-institutes:grid.12527.33
113 schema:familyName Steinberger
114 schema:givenName John
115 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010755664661.02
116 rdf:type schema:Person
117 sg:person.011041256670.23 schema:affiliation grid-institutes:grid.263333.4
118 schema:familyName Lee
119 schema:givenName Jooyoung
120 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011041256670.23
121 rdf:type schema:Person
122 sg:person.011724731171.01 schema:affiliation grid-institutes:None
123 schema:familyName Seurin
124 schema:givenName Yannick
125 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011724731171.01
126 rdf:type schema:Person
127 sg:person.012620015221.67 schema:affiliation grid-institutes:grid.33565.36
128 schema:familyName Gaži
129 schema:givenName Peter
130 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012620015221.67
131 rdf:type schema:Person
132 sg:person.014325641465.55 schema:affiliation grid-institutes:grid.133342.4
133 schema:familyName Tessaro
134 schema:givenName Stefano
135 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014325641465.55
136 rdf:type schema:Person
137 grid-institutes:None schema:alternateName ANSSI, Paris, France
138 schema:name ANSSI, Paris, France
139 rdf:type schema:Organization
140 grid-institutes:grid.12527.33 schema:alternateName Tsinghua University, Beijing, People’s Republic of China
141 schema:name Tsinghua University, Beijing, People’s Republic of China
142 rdf:type schema:Organization
143 grid-institutes:grid.133342.4 schema:alternateName UC Santa Barbara, Santa Barbara, USA
144 schema:name UC Santa Barbara, Santa Barbara, USA
145 rdf:type schema:Organization
146 grid-institutes:grid.263333.4 schema:alternateName Sejong University, Seoul, Korea
147 schema:name Sejong University, Seoul, Korea
148 rdf:type schema:Organization
149 grid-institutes:grid.33565.36 schema:alternateName IST Austria, Klosterneuburg, Austria
150 schema:name IST Austria, Klosterneuburg, Austria
151 rdf:type schema:Organization
 




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


...