From d6cf9819f0e8d43acab26ab2a11e458cfadcfd6f Mon Sep 17 00:00:00 2001 From: Mark Wooding Date: Wed, 11 Oct 2017 01:59:16 +0100 Subject: [PATCH] doc/wrestlers.tex: Update and fix. Also, add explicit bibliography. The bibliography is extracted from the upstream version. --- doc/wrestlers.bib | 985 ++++++++++++ doc/wrestlers.tex | 4547 +++++++++++++++++++++++++++++++++++++++++------------ 2 files changed, 4530 insertions(+), 1002 deletions(-) create mode 100644 doc/wrestlers.bib diff --git a/doc/wrestlers.bib b/doc/wrestlers.bib new file mode 100644 index 00000000..d49b548c --- /dev/null +++ b/doc/wrestlers.bib @@ -0,0 +1,985 @@ + + +,-------------------. +| PREAMBLE | +`-------------------' + +@preamble{ " \ifx\url\undefined\let\url\texttt\fi + \ifx\msgid\undefined\let\msgid\texttt\fi + \let\mdwxxthebibliography\thebibliography + \def\thebibliography{\mdwxxbibhook\mdwxxthebibliography} + \def\mdwxxurl#1{[#1]} + \def\biburl#1{\let\biburlsep\empty\biburlxi#1;;\done} + \def\biburlxi#1;{\def\temp{#1}\ifx\temp\empty\expandafter\biburlxiii\else + \biburlxii#1,,\done\let\biburlxafter\biburlxi\expandafter\biburlxmunch\fi} + \def\biburlxii#1,{\def\temp{#1}\ifx\temp\empty\expandafter\biburlxiii\else + \biburlsep\mdwxxurl{#1}\def\biburlsep{, }\let\biburlxafter\biburlxii + \expandafter\biburlxmunch\fi} \def\biburlxiii#1\done{} + \def\biburlxmunch{\futurelet\next\biburlxmunchi} + \def\biburlxmunchi{\expandafter\ifx\space\next\expandafter\biburlxmunchii + \else\expandafter\biburlxafter\fi} + \expandafter\def\expandafter\biburlxmunchii\space{\biburlxmunch} + \def\mdwxxbibhook{\let\mdwxxurl\url\let\url\biburl} \ifx \k \undefined \let + \k = \c \immediate\write16{Ogonek accent unavailable: replaced by cedilla} + \fi\input bibnames.sty\input path.sty\ifx \undefined \mathrm \def \mathrm + #1{{\rm #1}}\fi\hyphenation{ Cher-vo-nen-kis Eh-ren-feucht Hal-pern Jean-ette + Kam-eda Leigh-ton Mehl-horn Metro-po-lis Pra-sad Prep-a-ra-ta Press-er + Pros-ku-row-ski Ros-en-krantz Ru-dolph Schie-ber Schnei-der Te-zu-ka + Vis-wa-na-than Yech-ez-kel Yech-i-ali data-base data-bases dead-lock + poly-adic }\ifx \undefined \mathbb \def \mathbb #1{{\bf #1}}\fi\hyphenation{ + Ay-ka-nat Giun-chi-glia Lakh-neche Mal-er-ba Mart-el-li Reut-e-nau-er + Thiel-sch-er }\ifx \undefined \mathbf \def \mathbf #1{{\bf #1}}\fi\ifx + \undefined \TM \def \TM {${}^{\sc TM}$} \fi\hyphenation{ Ay-ka-nat + Giun-chi-glia Lakh-neche Mal-er-ba Mart-el-li Reut-e-nau-er Thiel-sch-er + }\ifx \undefined \eth \def \eth {{\font\ethfont = msbm10 \ethfont g}} \fi\ifx + \undefined \mathbb \def \mathbb #1{{\bf #1}}\fi\ifx \undefined \mathcal \def + \mathcal #1{{\cal #1}}\fi\ifx \undefined \TM \def \TM {${}^{\sc TM}$} + \fi\hyphenation{ Ay-ka-nat Giun-chi-glia Lakh-neche Mal-er-ba Mart-el-li + Reut-e-nau-er Thiel-sch-er }\ifx \undefined \bbb \def \bbb #1{\mathbb{#1}} + \fi\ifx \undefined \circled \def \circled #1{(#1)}\fi\ifx \undefined \mathbb + \def \mathbb #1{{\bf #1}}\fi\ifx \undefined \mathbf \def \mathbf #1{{\bf + #1}}\fi\ifx \undefined \mathcal \def \mathcal #1{{\cal #1}}\fi\ifx \undefined + \mathrm \def \mathrm #1{{\rm #1}}\fi\ifx \undefined \ocirc \def \ocirc + #1{{\accent'27#1}}\fi\ifx \undefined \reg \def \reg {\circled{R}}\fi\ifx + \undefined \TM \def \TM {${}^{\sc TM}$} \fi\hyphenation{ }\ifx \undefined + \cprime \def \cprime {$\mathsurround=0pt '$}\fi\ifx \undefined \Dbar \def + \Dbar {\leavevmode\raise0.2ex\hbox{--}\kern-0.5emD} \fi\ifx \undefined + \mathbb \def \mathbb #1{{\bf #1}}\fi\ifx \undefined \mathrm \def \mathrm + #1{{\rm #1}}\fi\ifx \undefined \operatorname \def \operatorname #1{{\rm + #1}}\fi\hyphenation{ Aba-di Arch-ives Ding-yi for-ge-ry Go-pa-la-krish-nan + Hi-de-ki Kraw-czyk Lands-verk Law-rence Leigh-ton Mich-ael Moell-er + North-ridge para-digm para-digms Piep-rzyk Piv-e-teau Ram-kilde + Re-tro-fit-ting Rich-ard Sho-stak Si-ro-mo-n-ey Ste-ph-en The-o-dore Tho-m-as + Tzone-lih venge-ance Will-iam Ye-sh-i-va }\ifx \undefined \bbb \def \bbb + #1{\mathbb{#1}} \fi\ifx \undefined \circled \def \circled #1{(#1)}\fi\ifx + \undefined \cprime \def \cprime {$\mathsurround=0pt '$}\fi\ifx \undefined + \mathbb \def \mathbb #1{{\bf #1}}\fi\ifx \undefined \mathrm \def \mathrm + #1{{\rm #1}}\fi\ifx \undefined \reg \def \reg {\circled{R}}\fi\ifx \undefined + \TM \def \TM {${}^{\sc TM}$} \fi\hyphenation{ Aba-di Arch-ives Ding-yi + for-ge-ry Go-pa-la-krish-nan Hi-de-ki Kraw-czyk Lands-verk Law-rence + Leigh-ton Mich-ael Moell-er North-ridge para-digm para-digms Piep-rzyk + Piv-e-teau Ram-kilde Re-tro-fit-ting Rich-ard Sho-stak Si-ro-mo-n-ey + Ste-ph-en The-o-dore Tho-m-as Tzone-lih venge-ance Will-iam Ye-sh-i-va }\ifx + \undefined \bbb \def \bbb #1{\mathbb{#1}} \fi\ifx \undefined \cprime \def + \cprime {$\mathsurround=0pt '$}\fi\ifx \undefined \mathbb \def \mathbb + #1{{\bf #1}}\fi\ifx \undefined \mathcal \def \mathcal #1{{\cal #1}}\fi\ifx + \undefined \mathrm \def \mathrm #1{{\rm #1}}\fi\hyphenation{ }\ifx \undefined + \cprime \def \cprime {$\mathsurround=0pt '$}\fi\ifx \undefined \Dbar \def + \Dbar {\leavevmode\raise0.2ex\hbox{--}\kern-0.5emD} \fi\ifx \undefined + \mathbb \def \mathbb #1{{\bf #1}}\fi\ifx \undefined \mathrm \def \mathrm + #1{{\rm #1}}\fi\ifx \undefined \operatorname \def \operatorname #1{{\rm + #1}}\fi\hyphenation{ Aba-di Arch-ives Ding-yi for-ge-ry Go-pa-la-krish-nan + Hi-de-ki Kraw-czyk Lands-verk Law-rence Leigh-ton Mich-ael Moell-er + North-ridge para-digm para-digms Piep-rzyk Piv-e-teau Ram-kilde + Re-tro-fit-ting Rich-ard Sho-stak Si-ro-mo-n-ey Ste-ph-en The-o-dore Tho-m-as + Tzone-lih venge-ance Will-iam Ye-sh-i-va }" +} + +,-------------------. +| BIBTEX ENTRIES | +`-------------------' + +@misc{cryptoeprint:2006:337, + author = {D.R. Stinson and J. Wu}, + howpublished = {Cryptology ePrint Archive, Report 2006/337}, + title = {An Efficient and Secure Two-flow Zero-Knowledge + Identification Protocol}, + year = {2006}, + url = {http://eprint.iacr.org/2006/337}, +} + +@misc{cryptoeprint:1999:012, + author = {Victor Shoup}, + howpublished = {Cryptology ePrint Archive, Report 1999/012}, + title = {On Formal Models for Secure Key Exchange}, + year = {1999}, + url = {http://eprint.iacr.org/1999/012}, +} + +@misc{cryptoeprint:2006:229, + author = {Neal Koblitz and Alfred Menezes}, + howpublished = {Cryptology ePrint Archive, Report 2006/229}, + title = {Another Look at "Provable Security". II}, + year = {2006}, + url = {http://eprint.iacr.org/2006/229}, +} + +@inproceedings{Bellare:1994:SCB, + address = {Berlin, Germany~/ Heidelberg, Germany~/ London, UK~/ + etc.}, + author = {Mihir Bellare and Joe Kilian and Phillip Rogaway}, + booktitle = {{Advances in cryptology, {CRYPTO '94}: 14th annual + international cryptology conference, Santa Barbara, + California, {USA}, August 21--25, 1994: proceedings}}, + editor = {Yvo G. Desmedt}, + pages = {341--358}, + publisher = {Spring{\-}er-Ver{\-}lag}, + series = {Lecture Notes in Computer Science}, + title = {The Security of Cipher Block Chaining}, + volume = {839}, + year = {1994}, + doi = {????}, + isbn = {3-540-58333-5 (Berlin), 0-387-58333-5 (New York)}, + issn = {0302-9743 (print), 1611-3349 (electronic)}, + url = {http://link.springer-ny.com/link/service/series/0558/bibs/ + 0839/08390341.htm; http://link.springer-ny.com/link/service/ + series/0558/papers/0839/08390341.pdf}, +} + +@inproceedings{Bellare:1995:XMN, + address = {Berlin, Germany~/ Heidelberg, Germany~/ London, UK~/ + etc.}, + author = {Mihir Bellare and Roch Gu{\'e}rin and + Phillip Rogaway}, + booktitle = {{Advances in cryptology, {CRYPTO '95}: 15th Annual + International Cryptology Conference, Santa Barbara, + California, {USA}, August 27--31, 1995: proceedings}}, + editor = {Don Coppersmith}, + note = {Sponsored by the International Association for + Cryptologic Research (IACR), in cooperation with the + IEEE Computer Society Technical Committee on Security + and Privacy.}, + pages = {15--35}, + publisher = {Spring{\-}er-Ver{\-}lag}, + series = {Lecture Notes in Computer Science}, + title = {{XOR MACs}: New methods for message authentication + using finite pseudorandom functions}, + volume = {963}, + year = {1995}, + doi = {????}, + isbn = {3-540-60221-6 (Berlin)}, + issn = {0302-9743 (print), 1611-3349 (electronic)}, + url = {http://link.springer-ny.com/link/service/series/0558/tocs/ + t0963.htm; http://www.springerlink.com/openurl.asp? + genre=issue&issn=0302-9743&volume=963}, +} + +@inproceedings{Bellare:1995:OAE, + address = {Berlin, Germany~/ Heidelberg, Germany~/ London, UK~/ + etc.}, + author = {M. Bellare and P. Rogaway}, + booktitle = {Advances in cryptology --- {EUROCRYPT} '94: Workshop + on the Theory and Application of Cryptographic + Techniques, Perugia, Italy, May 9--12, 1994: + proceedings}, + editor = {Alfredo {De Santis}}, + pages = {92--111}, + publisher = {Spring{\-}er-Ver{\-}lag}, + series = {Lecture Notes in Computer Science}, + title = {Optimal asymmetric encryption}, + volume = {950}, + year = {1995}, + isbn = {3-540-60176-7}, + issn = {0302-9743 (print), 1611-3349 (electronic)}, + url = {http://link.springer-ny.com/link/service/series/0558/bibs/ + 0950/09500092.htm; http://link.springer-ny.com/link/service/ + series/0558/papers/0950/09500092.pdf}, +} + +@article{Bellare:1996:ESD, + author = {Mihir Bellare and Phillip Rogaway}, + journal = {Lecture Notes in Computer Science}, + pages = {399--??}, + title = {The exact security of digital signatures --- how to + sign with {RSA} and {Rabin}}, + volume = {1070}, + year = {1996}, + issn = {0302-9743 (print), 1611-3349 (electronic)}, + url = {http://link.springer-ny.com/link/service/series/0558/bibs/ + 1070/10700399.htm; http://link.springer-ny.com/link/service/ + series/0558/papers/1070/10700399.pdf}, +} + +@inproceedings{Bellare:1996:KHF, + address = {Berlin, Germany~/ Heidelberg, Germany~/ London, UK~/ + etc.}, + author = {Mihir Bellare and Ran Canetti and Hugo Krawczyk}, + booktitle = {{Advances in cryptology, {CRYPTO '96}: 16th annual + international cryptology conference, Santa Barbara, + California, {USA}, August 18--22, 1996: proceedings}}, + editor = {Neal Koblitz}, + note = {Sponsored by the International Association for + Cryptologic Research (IACR), in cooperation with the + IEEE Computer Society Technical Committee on Security + and Privacy and the Computer Science Department of + the University of California at Santa Barbara + (UCSB).}, + pages = {1--15}, + publisher = {Spring{\-}er-Ver{\-}lag}, + series = {Lecture Notes in Computer Science}, + title = {Keying Hash Functions for Message Authentication}, + volume = {1109}, + year = {1996}, + annote = {``Sponsored by the International Association for + Cryptologic Research (IACR), in cooperation with the + IEEE Computer Society Technical Committee on Security + and Privacy and the Computer Science Department of + the University of California at Santa Barbara + (UCSB)''}, + doi = {????}, + isbn = {3-540-61512-1}, + issn = {0302-9743 (print), 1611-3349 (electronic)}, + url = {Full version: http://www.research.ibm.com/security/; http:// + link.springer-ny.com/link/service/series/0558/bibs/1109/ + 11090001.htm; http://link.springer-ny.com/link/service/ + series/0558/papers/1109/11090001.pdf}, +} + +@inproceedings{Bellare:1997:CST, + address = {1109 Spring Street, Suite 300, Silver Spring, MD + 20910, USA}, + author = {M. Bellare and A. Desai and E. Jokipii and + P. Rogaway}, + booktitle = {38th Annual Symposium on Foundations of Computer + Science: October 20--22, 1997, Miami Beach, Florida}, + editor = {{IEEE}}, + note = {IEEE catalog number 97CB36150. IEEE Computer Society + Press order number PR08197.}, + pages = {394--403}, + publisher = {IEEE Computer Society Press}, + title = {A concrete security treatment of symmetric + encryption}, + year = {1997}, + isbn = {0-8186-8197-7, 0-8186-8198-5 (casebound), + 0-8186-8199-3 (microfiche)}, + issn = {0272-5428}, +} + +@article{Bellare:1999:POP, + author = {M. Bellare}, + journal = {Lecture Notes in Computer Science}, + pages = {1--15}, + title = {Practice-Oriented Provable Security}, + volume = {1561}, + year = {1999}, + issn = {0302-9743 (print), 1611-3349 (electronic)}, +} + +@techreport{Burrows:1989:LAa, + author = {Michael Burrows and Martin Abadi and Roger Needham}, + institution = {Digital Equipment Corporation, Systems Research + Centre}, + month = feb, + number = {39}, + pages = {48}, + title = {A Logic of Authentication}, + year = {1989}, + abstract = {Questions of belief are essential in analyzing + protocols for authentication in distributed computing + systems. In this paper we motivate, set out, and + exemplify a logic specifically designed for this + analysis; we show how various protocols differ subtly + with respect to the required initial assumptions of + the participants and their final beliefs. Our + formalism has enabled us to isolate and express these + differences with a precision that was not previously + possible. It has drawn attention to features of + protocols of which we and their authors were + previously unaware, and allowed us to suggest + improvements to the protocols. The reasoning about + some protocols has been mechanically verified. This + paper starts with an informal account of the problem, + goes on to explain the formalism to be used, and + gives examples of its application to protocols from + the literature, both with conventional shared-key + cryptography and with public-key cryptography. Some + of the examples are chosen because of their practical + importance, while others serve to illustrate subtle + points of the logic and to explain how we use it. We + discuss extensions of the logic motivated by actual + practice -- for example, in order to account for the + use of hash functions in signatures. The final + sections contain a formal semantics of the logic and + some conclusions.}, +} + +@inproceedings{Bellare:1994:EAK, + address = {Berlin, Germany~/ Heidelberg, Germany~/ London, UK~/ + etc.}, + author = {Mihir Bellare and Phillip Rogaway}, + booktitle = {{Advances in cryptology, {CRYPTO '94}: 14th annual + international cryptology conference, Santa Barbara, + California, {USA}, August 21--25, 1994: proceedings}}, + editor = {Yvo G. Desmedt}, + pages = {232--249}, + publisher = {Spring{\-}er-Ver{\-}lag}, + series = {Lecture Notes in Computer Science}, + title = {Entity Authentication and Key Distribution}, + volume = {839}, + year = {1994}, + doi = {????}, + isbn = {3-540-58333-5 (Berlin), 0-387-58333-5 (New York)}, + issn = {0302-9743 (print), 1611-3349 (electronic)}, + url = {http://link.springer-ny.com/link/service/series/0558/bibs/ + 0773/07730232.htm; http://link.springer-ny.com/link/service/ + series/0558/papers/0773/07730232.pdf}, +} + +@inproceedings{Bellare:1995:PSS, + address = {New York, NY, USA}, + author = {Mihir Bellare and Phillip Rogaway}, + booktitle = {Proceedings of the twenty-seventh annual {ACM} + Symposium on Theory of Computing: Las Vegas, Nevada, + May 29--June 1, 1995}, + editor = {{ACM}}, + note = {ACM order no. 508950.}, + pages = {57--66}, + publisher = {ACM Press}, + title = {Provably secure session key distribution: the three + party case}, + year = {1995}, + isbn = {0-89791-718-9}, + url = {http://www.acm.org/pubs/citations/proceedings/stoc/225058/ + p57-bellare/; http://www.acm.org/pubs/articles/proceedings/ + stoc/225058/p57-bellare/p57-bellare.pdf}, +} + +@article{Blake-Wilson:1997:KAP, + author = {S. Blake-Wilson and D. Johnson and A. Menezes}, + journal = {Lecture Notes in Computer Science}, + pages = {30--??}, + title = {Key Agreement Protocols and Their Security Analysis}, + volume = {1355}, + year = {1997}, + issn = {0302-9743}, +} + +@article{Blake-Wilson:1998:EAA, + author = {S. Blake-Wilson and A. Menezes}, + journal = {Lecture Notes in Computer Science}, + pages = {137--??}, + title = {Entity Authentication and Authenticated Key Transport + Protocols Employing Asymmetric Techniques}, + volume = {1361}, + year = {1998}, + issn = {0302-9743}, +} + +@inproceedings{Bellare:1998:MAD, + address = {New York, NY, USA}, + author = {Mihir Bellare and Ran Canetti and Hugo Krawczyk}, + booktitle = {Proceedings of the thirtieth annual {ACM} Symposium + on Theory of Computing: Dallas, Texas, May 23--26, + 1998}, + editor = {{ACM}}, + note = {ACM order number 508980.}, + pages = {419--428}, + publisher = {ACM Press}, + title = {A modular approach to the design and analysis of + authentication and key exchange protocols (extended + abstract)}, + year = {1998}, + isbn = {0-89791-962-9}, + url = {http://www.acm.org/pubs/citations/proceedings/stoc/276698/ + p419-bellare/; http://www.acm.org/pubs/articles/proceedings/ + stoc/276698/p419-bellare/p419-bellare.pdf}, +} + +@misc{cryptoeprint:2001:040, + author = {Ran Canetti and Hugo Krawczyk}, + howpublished = {Cryptology ePrint Archive, Report 2001/040}, + title = {Analysis of Key-Exchange Protocols and Their Use for + Building Secure Channels}, + year = {2001}, + url = {http://eprint.iacr.org/2001/040}, +} + +@article{Canetti:2001:AKE, + author = {Ran Canetti and Hugo Krawczyk}, + journal = {Lecture Notes in Computer Science}, + pages = {453--??}, + title = {Analysis of Key-Exchange Protocols and Their Use for + Building Secure Channels}, + volume = {2045}, + year = {2001}, + issn = {0302-9743}, + url = {http://link.springer-ny.com/link/service/series/0558/bibs/ + 2045/20450453.htm; http://link.springer-ny.com/link/service/ + series/0558/papers/2045/20450453.pdf}, +} + +@techreport{Canetti:2001:UCS, + author = {Ran Canetti}, + institution = {Cryptology {ePrint} Archive}, + month = oct, + note = {Extended Abstract appeared in proceedings of the 42nd + Symposium on Foundations of Computer Science (FOCS), + 2001}, + number = {2000/067}, + type = {Report}, + title = {Universally Composable Security: {A} New Paradigm for + Cryptographic Protocols}, + year = {2001}, + abstract = {We propose a new paradigm for defining security of + cryptographic protocols, called {\sf universally + composable security.} The salient property of + universally composable definitions of security is + that they guarantee security even when a secure + protocol is composed with an arbitrary set of + protocols, or more generally when the protocol is + used as a component of an arbitrary system. This is + an essential property for maintaining security of + cryptographic protocols in complex and unpredictable + environments such as the Internet. In particular, + universally composable definitions guarantee security + even when an unbounded number of protocol instances + are executed concurrently in an adversarially + controlled manner, they guarantee non-malleability + with respect to arbitrary protocols, and more. We + show how to formulate universally composable + definitions of security for practically any + cryptographic task. Furthermore, we demonstrate that + practically any such definition can be realized using + known general techniques, as long as only a minority + of the participants are corrupted. We then proceed to + formulate universally composable definitions of a + wide array of cryptographic tasks, including + authenticated and secure communication, key-exchange, + public-key encryption, signature, commitment, + oblivious transfer, zero-knowledge, and more. We also + make initial steps towards studying the realizability + of the proposed definitions in other natural + settings.}, + annote = {Revised version of \cite{Canetti:2000:SCM}.}, + url = {http://eprint.iacr.org/2000/067}, +} + +@article{Canetti:2002:UCN, + author = {Ran Canetti and Hugo Krawczyk}, + journal = {Lecture Notes in Computer Science}, + pages = {337--??}, + title = {Universally Composable Notions of Key Exchange and + Secure Channels}, + volume = {2332}, + year = {2002}, + issn = {0302-9743 (print), 1611-3349 (electronic)}, + url = {http://link.springer-ny.com/link/service/series/0558/bibs/ + 2332/23320337.htm; http://link.springer-ny.com/link/service/ + series/0558/papers/2332/23320337.pdf}, +} + +@misc{cryptoeprint:2004:332, + author = {Victor Shoup}, + howpublished = {Cryptology ePrint Archive, Report 2004/332}, + title = {Sequences of games: a tool for taming complexity in + security proofs}, + year = {2004}, + url = {http://eprint.iacr.org/2004/332}, +} + +@misc{cryptoeprint:2004:331, + author = {Mihir Bellare and Phillip Rogaway}, + howpublished = {Cryptology ePrint Archive, Report 2004/331}, + title = {Code-Based Game-Playing Proofs and the Security of + Triple Encryption}, + year = {2004}, + url = {http://eprint.iacr.org/2004/331}, +} + +@inproceedings{Shoup:2001:OR, + address = {Berlin, Germany~/ Heidelberg, Germany~/ London, UK~/ + etc.}, + author = {Victor Shoup}, + booktitle = {Advances in cryptology --- {CRYPTO} 2001: 21st Annual + International Cryptology Conference, Santa Barbara, + California, {USA}, August 19--23, 2001: proceedings}, + editor = {Joe Kilian}, + pages = {239--??}, + publisher = {Spring{\-}er-Ver{\-}lag}, + series = {Lecture Notes in Computer Science}, + title = {{OAEP} Reconsidered}, + volume = {2139}, + year = {2001}, + isbn = {3-540-42456-3 (paperback)}, + url = {http://link.springer-ny.com/link/service/series/0558/bibs/ + 2139/21390239.htm; http://link.springer-ny.com/link/service/ + series/0558/papers/2139/21390239.pdf}, +} + +@inproceedings{Bellare:1993:ROP, + author = {Mihir Bellare and Phillip Rogaway}, + booktitle = {Proceedings of the First Annual Conference on + Computer and Communications Security}, + organization = {{ACM}}, + pages = {62--73}, + title = {Random oracles are practical}, + year = {1993}, + url = {http://www-cse.ucsd.edu/users/mihir/papers/ro.html}, +} + +@article{Canetti:2004:ROM, + author = {Ran Canetti and Oded Goldreich and Shai Halevi}, + journal = {Journal of the ACM}, + month = jul, + number = {4}, + pages = {557--594}, + title = {The random oracle methodology, revisited}, + volume = {51}, + year = {2004}, + issn = {0004-5411 (print), 1557-735X (electronic)}, +} + +@article{Boneh:2003:IBE, + author = {Dan Boneh and Matthew Franklin}, + journal = {SIAM Journal on Computing}, + month = jun, + number = {3}, + pages = {586--615}, + title = {Identity-Based Encryption from the {Weil} Pairing}, + volume = {32}, + year = {2003}, + doi = {http://dx.doi.org/10.1137/S0097539701398521}, + issn = {0097-5397 (print), 1095-7111 (electronic)}, + url = {http://epubs.siam.org/sam-bin/dbq/article/39852}, +} + +@article{Shoup:1997:LBD, + author = {Victor Shoup}, + journal = {Lecture Notes in Computer Science}, + pages = {256--??}, + title = {Lower Bounds for Discrete Logarithms and Related + Problems}, + volume = {1233}, + year = {1997}, + issn = {0302-9743}, + url = {http://link.springer-ny.com/link/service/series/0558/bibs/ + 1233/12330256.htm; http://link.springer-ny.com/link/service/ + series/0558/papers/1233/12330256.pdf}, +} + +@article{Boneh:1998:DDP, + author = {D. Boneh}, + journal = {Lecture Notes in Computer Science}, + pages = {48--63}, + title = {The Decision {Diffie--Hellman} Problem}, + volume = {1423}, + year = {1998}, + issn = {0302-9743 (print), 1611-3349 (electronic)}, + url = {http://theory.stanford.edu/~dabo/papers/DDH.ps.gz}, +} + +@article{Bellare:1998:RAN, + author = {Mihir Bellare and Anand Desai and David Pointcheval and + Phillip Rogaway}, + journal = {Lecture Notes in Computer Science}, + pages = {26--??}, + title = {Relations Among Notions of Security for Public-Key + Encryption Schemes}, + volume = {1462}, + year = {1998}, + issn = {0302-9743 (print), 1611-3349 (electronic)}, + url = {http://link.springer-ny.com/link/service/series/0558/bibs/ + 1462/14620026.htm; http://link.springer-ny.com/link/service/ + series/0558/papers/1462/14620026.pdf}, +} + +@inproceedings{ElGamal:1985:PKCb, + address = {Berlin, Germany~/ Heidelberg, Germany~/ London, UK~/ + etc.}, + author = {Taher ElGamal}, + booktitle = {{Advances in Cryptology: Proceedings of CRYPTO 84}}, + editor = {George Robert Blakley and David Chaum}, + note = {CRYPTO 84: a Workshop on the Theory and Application + of Cryptographic Techniques, held at the University + of California, Santa Barbara, August 19--22, 1984, + sponsored by the International Association for + Cryptologic Research.}, + pages = {10--18}, + publisher = {Spring{\-}er-Ver{\-}lag}, + series = {Lecture Notes in Computer Science}, + title = {A Public Key Cryptosystem and a Signature Scheme + Based on Discrete Logarithms}, + volume = {196}, + year = {1985}, + doi = {http://dx.doi.org/10.1007/3-540-39568-7}, + isbn = {0-387-15658-5; 3-540-39568-7}, + issn = {0302-9743 (print), 1611-3349 (electronic)}, + url = {http://www.springerlink.com/openurl.asp?genre=article&issn=? + ???&volume=0&issue=0&spage=10}, +} + +@misc{Menezes:2005:IPB, + author = {Alfred Menezes}, + note = {Notes from lectures given in Santander, Spain}, + title = {An Introduction to Pairing-Based Cryptography}, + year = {2005}, + url = {http://www.cacr.math.uwaterloo.ca/~ajmeneze/publications/ + pairings.pdf}, +} + +@book{Schneier:1996:ACP, + address = {New York, NY, USA}, + author = {Bruce Schneier}, + edition = {Second}, + pages = {xxiii + 758}, + publisher = {John Wiley and Sons, Inc.}, + title = {Applied Cryptography: Protocols, Algorithms, and + Source Code in {C}}, + year = {1996}, + isbn = {0-471-12845-7 (cloth), 0-471-11709-9 (paper)}, + url = {http://www.counterpane.com/applied.html}, +} + +@misc{SEC1, + author = {{Certicom Research}}, + title = {Standards for Efficient Cryptography, {SEC} 1: + {E}lliptic curve cryptography, Version 1.0}, + year = {2000}, + url = {http://www.secg.org/download/aid-385/sec1_final.pdf}, +} + +@misc{cryptoeprint:2006:280, + author = {Mario Di Raimondo and Rosario Gennaro and + Hugo Krawczyk}, + howpublished = {Cryptology ePrint Archive, Report 2006/280}, + title = {Deniable Authentication and Key Exchange}, + year = {2006}, + url = {http://eprint.iacr.org/2006/280}, +} + +@misc{rfc793, + author = {J. Postel}, + howpublished = {RFC 793 (Standard)}, + month = sep, + note = {Updated by RFCs 1122, 3168}, + number = {793}, + publisher = {IETF}, + series = {Request for Comments}, + title = {{Transmission Control Protocol}}, + year = {1981}, + url = {http://www.ietf.org/rfc/rfc793.txt}, +} + +@misc{rfc768, + author = {J. Postel}, + howpublished = {RFC 768 (Standard)}, + month = aug, + number = {768}, + publisher = {IETF}, + series = {Request for Comments}, + title = {{User Datagram Protocol}}, + year = {1980}, + url = {http://www.ietf.org/rfc/rfc768.txt}, +} + +@incollection{Bellare:2000:AER, + address = {Berlin, Germany~/ Heidelberg, Germany~/ London, UK~/ + etc.}, + author = {Mihir Bellare and Chanathip Namprempre}, + booktitle = {Advances in cryptology---ASIACRYPT 2000 (Kyoto)}, + pages = {531--545}, + publisher = {Spring{\-}er-Ver{\-}lag}, + series = {Lecture Notes in Comput. Sci.}, + title = {Authenticated Encryption: Relations among Notions and + Analysis of the Generic Composition Paradigm}, + volume = {1976}, + year = {2000}, + url = {http://link.springer-ny.com/link/service/series/0558/bibs/ + 1976/19760531.htm; http://link.springer-ny.com/link/service/ + series/0558/papers/1976/19760531.pdf}, +} + +@inproceedings{Krawczyk:2001:OEA, + address = {Berlin, Germany~/ Heidelberg, Germany~/ London, UK~/ + etc.}, + author = {Hugo Krawczyk}, + booktitle = {Advances in cryptology --- {CRYPTO} 2001: 21st Annual + International Cryptology Conference, Santa Barbara, + California, {USA}, August 19--23, 2001: proceedings}, + editor = {Joe Kilian}, + pages = {310--??}, + publisher = {Spring{\-}er-Ver{\-}lag}, + series = {Lecture Notes in Computer Science}, + title = {The Order of Encryption and Authentication for + Protecting Communications (or: How Secure Is {SSL}?)}, + volume = {2139}, + year = {2001}, + isbn = {3-540-42456-3 (paperback)}, + url = {http://link.springer-ny.com/link/service/series/0558/bibs/ + 2139/21390310.htm; http://link.springer-ny.com/link/service/ + series/0558/papers/2139/21390310.pdf}, +} + +@article{Rogaway:2003:OBC, + author = {Phillip Rogaway and Mihir Bellare and John Black}, + journal = {ACM Transactions on Information and System Security}, + month = aug, + number = {3}, + pages = {365--403}, + title = {{OCB}: {A} block-cipher mode of operation for + efficient authenticated encryption}, + volume = {6}, + year = {2003}, + issn = {1094-9224 (print), 1557-7406 (electronic)}, +} + +@inproceedings{Bellare:2004:EAX, + author = {Mihir Bellare and Phillip Rogaway and David Wagner}, + booktitle = {FSE}, + editor = {Bimal K. Roy and Willi Meier}, + pages = {389--407}, + publisher = {Springer}, + series = {Lecture Notes in Computer Science}, + title = {The {EAX} Mode of Operation}, + volume = {3017}, + year = {2004}, + isbn = {3-540-22171-9}, + url = {http://www.cs.berkeley.edu/~daw/papers/eax-fse04.ps}, +} + +@inproceedings{McGrew:2004:SPG, + author = {David A. McGrew and John Viega}, + booktitle = {Progress in Cryptology - {INDOCRYPT} 2004, 5th + International Conference on Cryptology in India, + Chennai, India, December 20-22, 2004, Proceedings}, + editor = {Anne Canteaut and Kapalee Viswanathan}, + pages = {343--355}, + publisher = {Springer}, + series = {Lecture Notes in Computer Science}, + title = {The Security and Performance of the Galois/Counter + Mode ({GCM}) of Operation}, + volume = {3348}, + year = {2004}, + isbn = {3-540-24130-2}, + url = {http://eprint.iacr.org/2004/193}, +} + +@inproceedings{Rogaway:2002:AEA, + address = {Washington, DC, USA}, + author = {Phillip Rogaway}, + booktitle = {Proceedings of the 9th {ACM} Conference on Computer + and Communications Security}, + editor = {Ravi Sandhu}, + month = nov, + pages = {98--107}, + publisher = {ACM Press}, + title = {Authenticated-encryption with associated-data}, + year = {2002}, + abstract = {When a message is transformed into a ciphertext in a + way designed to protect both its privacy and + authenticity, there may be additional information, + such as a packet header, that travels alongside the + ciphertext (at least conceptually) and must get + authenticated with it. We formalize and investigate + this authenticated-encryption with associated-data + (AEAD) problem. Though the problem has long been + addressed in cryptographic practice, it was never + provided a definition or even a name. We do this, and + go on to look at efficient solutions for AEAD, both + in general and for the authenticated-encryption + scheme OCB. For the general setting we study two + simple ways to turn an authenticated-encryption + scheme that does not support associated-data into one + that does: nonce stealing and ciphertext translation. + For the case of OCB we construct an AEAD-scheme by + combining OCB and the pseudorandom function PMAC, + using the same key for both algorithms. We prove + that, despite ``interaction'' between the two schemes + when using a common key, the combination is sound. We + also consider achieving AEAD by the generic + composition of a nonce-based, privacy-only encryption + scheme and a pseudorandom function.}, + url = {http://www.cs.ucdavis.edu/~rogaway/papers/ad.html}, +} + +@proceedings{Desmedt:1994:ACC, + address = {Berlin, Germany~/ Heidelberg, Germany~/ London, UK~/ + etc.}, + booktitle = {{Advances in cryptology, {CRYPTO '94}: 14th annual + international cryptology conference, Santa Barbara, + California, {USA}, August 21--25, 1994: proceedings}}, + editor = {Yvo G. Desmedt}, + pages = {xii + 438}, + publisher = {Spring{\-}er-Ver{\-}lag}, + series = {Lecture Notes in Computer Science}, + title = {{Advances in cryptology, {CRYPTO '94}: 14th annual + international cryptology conference, Santa Barbara, + California, {USA}, August 21--25, 1994: proceedings}}, + volume = {839}, + year = {1994}, + doi = {????}, + isbn = {3-540-58333-5 (Berlin), 0-387-58333-5 (New York)}, + issn = {0302-9743 (print), 1611-3349 (electronic)}, + url = {http://link.springer-ny.com/link/service/series/0558/tocs/ + t0839.htm; http://www.springerlink.com/openurl.asp? + genre=issue&issn=0302-9743&volume=839}, +} + +@proceedings{Kilian:2001:ACC, + address = {Berlin, Germany~/ Heidelberg, Germany~/ London, UK~/ + etc.}, + booktitle = {Advances in cryptology --- {CRYPTO} 2001: 21st Annual + International Cryptology Conference, Santa Barbara, + California, {USA}, August 19--23, 2001: proceedings}, + editor = {Joe Kilian}, + pages = {xi + 598}, + publisher = {Spring{\-}er-Ver{\-}lag}, + series = {Lecture Notes in Computer Science}, + title = {Advances in cryptology --- {CRYPTO} 2001: 21st Annual + International Cryptology Conference, Santa Barbara, + California, {USA}, August 19--23, 2001: proceedings}, + volume = {2139}, + year = {2001}, + isbn = {3-540-42456-3 (paperback)}, + url = {http://link.springer-ny.com/link/service/series/0558/tocs/ + t2139.htm}, +} + +@proceedings{IEEE:1997:ASF, + address = {1109 Spring Street, Suite 300, Silver Spring, MD + 20910, USA}, + booktitle = {38th Annual Symposium on Foundations of Computer + Science: October 20--22, 1997, Miami Beach, Florida}, + editor = {{IEEE}}, + note = {IEEE catalog number 97CB36150. IEEE Computer Society + Press order number PR08197.}, + pages = {xiii + 606}, + publisher = {IEEE Computer Society Press}, + title = {38th Annual Symposium on Foundations of Computer + Science: October 20--22, 1997, Miami Beach, Florida}, + year = {1997}, + isbn = {0-8186-8197-7, 0-8186-8198-5 (casebound), + 0-8186-8199-3 (microfiche)}, + issn = {0272-5428}, +} + +@proceedings{ACM:1995:PTS, + address = {New York, NY, USA}, + booktitle = {Proceedings of the twenty-seventh annual {ACM} + Symposium on Theory of Computing: Las Vegas, Nevada, + May 29--June 1, 1995}, + editor = {{ACM}}, + note = {ACM order no. 508950.}, + pages = {viii + 763}, + publisher = {ACM Press}, + title = {Proceedings of the twenty-seventh annual {ACM} + Symposium on Theory of Computing: Las Vegas, Nevada, + May 29--June 1, 1995}, + year = {1995}, + isbn = {0-89791-718-9}, +} + +@proceedings{ACM:1998:PTA, + address = {New York, NY, USA}, + booktitle = {Proceedings of the thirtieth annual {ACM} Symposium + on Theory of Computing: Dallas, Texas, May 23--26, + 1998}, + editor = {{ACM}}, + note = {ACM order number 508980.}, + pages = {x + 684}, + publisher = {ACM Press}, + title = {Proceedings of the thirtieth annual {ACM} Symposium + on Theory of Computing: Dallas, Texas, May 23--26, + 1998}, + year = {1998}, + isbn = {0-89791-962-9}, +} + +@proceedings{DeSantis:1995:ACE, + address = {Berlin, Germany~/ Heidelberg, Germany~/ London, UK~/ + etc.}, + booktitle = {Advances in cryptology --- {EUROCRYPT} '94: Workshop + on the Theory and Application of Cryptographic + Techniques, Perugia, Italy, May 9--12, 1994: + proceedings}, + editor = {Alfredo {De Santis}}, + pages = {xiii + 472}, + publisher = {Spring{\-}er-Ver{\-}lag}, + series = {Lecture Notes in Computer Science}, + title = {Advances in cryptology --- {EUROCRYPT} '94: Workshop + on the Theory and Application of Cryptographic + Techniques, Perugia, Italy, May 9--12, 1994: + proceedings}, + volume = {950}, + year = {1995}, + isbn = {3-540-60176-7}, + issn = {0302-9743 (print), 1611-3349 (electronic)}, +} + +@proceedings{Coppersmith:1995:ACC, + address = {Berlin, Germany~/ Heidelberg, Germany~/ London, UK~/ + etc.}, + booktitle = {{Advances in cryptology, {CRYPTO '95}: 15th Annual + International Cryptology Conference, Santa Barbara, + California, {USA}, August 27--31, 1995: proceedings}}, + editor = {Don Coppersmith}, + note = {Sponsored by the International Association for + Cryptologic Research (IACR), in cooperation with the + IEEE Computer Society Technical Committee on Security + and Privacy.}, + pages = {xii + 465}, + publisher = {Spring{\-}er-Ver{\-}lag}, + series = {Lecture Notes in Computer Science}, + title = {{Advances in cryptology, {CRYPTO '95}: 15th Annual + International Cryptology Conference, Santa Barbara, + California, {USA}, August 27--31, 1995: proceedings}}, + volume = {963}, + year = {1995}, + doi = {????}, + isbn = {3-540-60221-6 (Berlin)}, + issn = {0302-9743 (print), 1611-3349 (electronic)}, + url = {http://link.springer-ny.com/link/service/series/0558/tocs/ + t0963.htm; http://www.springerlink.com/openurl.asp? + genre=issue&issn=0302-9743&volume=963}, +} + +@proceedings{Koblitz:1996:ACC, + address = {Berlin, Germany~/ Heidelberg, Germany~/ London, UK~/ + etc.}, + booktitle = {{Advances in cryptology, {CRYPTO '96}: 16th annual + international cryptology conference, Santa Barbara, + California, {USA}, August 18--22, 1996: proceedings}}, + editor = {Neal Koblitz}, + note = {Sponsored by the International Association for + Cryptologic Research (IACR), in cooperation with the + IEEE Computer Society Technical Committee on Security + and Privacy and the Computer Science Department of + the University of California at Santa Barbara + (UCSB).}, + pages = {xii + 415}, + publisher = {Spring{\-}er-Ver{\-}lag}, + series = {Lecture Notes in Computer Science}, + title = {{Advances in cryptology, {CRYPTO '96}: 16th annual + international cryptology conference, Santa Barbara, + California, {USA}, August 18--22, 1996: proceedings}}, + volume = {1109}, + year = {1996}, + annote = {``Sponsored by the International Association for + Cryptologic Research (IACR), in cooperation with the + IEEE Computer Society Technical Committee on Security + and Privacy and the Computer Science Department of + the University of California at Santa Barbara + (UCSB)''}, + doi = {????}, + isbn = {3-540-61512-1}, + issn = {0302-9743 (print), 1611-3349 (electronic)}, + url = {http://link.springer-ny.com/link/service/series/0558/tocs/ + t1109.htm; http://www.springerlink.com/openurl.asp? + genre=issue&issn=0302-9743&volume=1109}, +} + +@proceedings{Blakley:1985:ACP, + address = {Berlin, Germany~/ Heidelberg, Germany~/ London, UK~/ + etc.}, + booktitle = {{Advances in Cryptology: Proceedings of CRYPTO 84}}, + editor = {George Robert Blakley and David Chaum}, + note = {CRYPTO 84: a Workshop on the Theory and Application + of Cryptographic Techniques, held at the University + of California, Santa Barbara, August 19--22, 1984, + sponsored by the International Association for + Cryptologic Research.}, + pages = {ix + 491}, + publisher = {Spring{\-}er-Ver{\-}lag}, + series = {Lecture Notes in Computer Science}, + title = {{Advances in Cryptology: Proceedings of CRYPTO 84}}, + volume = {196}, + year = {1985}, + doi = {http://dx.doi.org/10.1007/3-540-39568-7}, + isbn = {0-387-15658-5; 3-540-39568-7}, + issn = {0302-9743 (print), 1611-3349 (electronic)}, + url = {http://link.springer-ny.com/link/service/series/0558/tocs/ + t0196.htm; http://www.springerlink.com/content/cemajg0qmeev/ + ; http://www.springerlink.com/openurl.asp?genre=issue& + issn=0302-9743&volume=196}, +} + diff --git a/doc/wrestlers.tex b/doc/wrestlers.tex index f2d9ac47..4ad36746 100644 --- a/doc/wrestlers.tex +++ b/doc/wrestlers.tex @@ -1,1145 +1,3688 @@ %%% -*-latex-*- %%% -%%% Description of the Wrestlers Protocol +%%% The Wrestlers Protocol: secure, deniable key-exchange %%% -%%% (c) 2001 Mark Wooding +%%% (c) 2006 Mark Wooding %%% -\newif\iffancystyle\fancystyletrue +\makeatletter +\def\@doit#1{#1} +\ifx\iffancystyle\xxundefined\expandafter\@doit\else\expandafter\@gobble\fi +{\newif\iffancystyle\fancystyletrue} +\ifx\ifshort\xxundefined\expandafter\@doit\else\expandafter\@gobble\fi +{\newif\ifshort\shortfalse} +\iffancystyle\expandafter\@gobble\else\expandafter\@doit\fi{\newif\ifpdfing} +\makeatother + +\typeout{Options:} +\typeout{ Fancy style: \iffancystyle ON\else OFF\fi} +\typeout{ Short version: \ifshort ON\else OFF\fi} + +\errorcontextlines=\maxdimen +\showboxdepth=\maxdimen +\showboxbreadth=\maxdimen \iffancystyle - \documentclass - [a4paper, article, 10pt, numbering, noherefloats, notitlepage] - {strayman} + \documentclass{strayman} + \parskip=0pt plus 1pt \parindent=1.2em + \usepackage[T1]{fontenc} \usepackage[palatino, helvetica, courier, maths=cmr]{mdwfonts} - \usepackage[mdwmargin]{mdwthm} - \PassOptionsToPackage{dvips}{xy} + \usepackage[within = subsection, mdwmargin]{mdwthm} + \usepackage{mdwlist} + \usepackage{sverb} + \ifpdfing\else + \PassOptionsToPackage{dvips}{xy} + \fi \else + \PassOptionsToClass{runningheads}{llncs} \documentclass{llncs} \fi -\usepackage{mdwtab, mathenv, mdwlist, mdwmath, crypto} +\PassOptionsToPackage{show}{slowbox} +%\PassOptionsToPackage{hide}{slowbox} +\usepackage{mdwtab, mdwmath, crypto} +\usepackage{slowbox} \usepackage{amssymb, amstext} +\usepackage{url, multicol} \usepackage{tabularx} -\usepackage{url} -\usepackage[all]{xy} - -\errorcontextlines=999 -\showboxbreadth=999 -\showboxdepth=999 -\makeatletter +\DeclareUrlCommand\email{\urlstyle{tt}} +\ifslowboxshow + \usepackage[all]{xy} + \turnradius{4pt} +\fi +\usepackage{mathenv} -\title{The Wrestlers Protocol: proof-of-receipt and secure key exchange} -\author{Mark Wooding \and Clive Jones} +\newcommand{\Nupto}[1]{\{0, 1, \ldots, #1 - 1\}} +\iffancystyle + \let\next\title +\else + \def\next[#1]{\titlerunning{#1}\title} +\fi +\next + [The Wrestlers Protocol] + {The Wrestlers Protocol% + \ifshort\thanks{This is an extended abstract; the full version + \cite{Wooding:2006:WP} is available from + \texttt{http://eprint.iacr.org/2006/386/}.}\fi \\ + A simple, practical, secure, deniable protocol for key-exchange} +\iffancystyle + \author{Mark Wooding \\ \email{mdw@distorted.org.uk}} +\else + \author{Mark Wooding} + \institute{\email{mdw@distorted.org.uk}} +\fi +\date{2 November 2006} -\bibliographystyle{mdwalpha} +\iffancystyle + \bibliographystyle{mdwalpha} + \let\epsilon\varepsilon + \let\emptyset\varnothing + \let\le\leqslant\let\leq\le + \let\ge\geqslant\let\geq\ge + \numberwithin{table}{section} + \numberwithin{figure}{section} + \numberwithin{equation}{subsection} + \let\random\$ +\else + \bibliographystyle{splncs} + \expandafter\let\csname claim*\endcsname\claim + \expandafter\let\csname endclaim*\endcsname\endclaim +\fi -\newcolumntype{G}{p{0pt}} -\def\Nupto#1{\N_{<{#1}}} \let\Bin\Sigma -\let\epsilon\varepsilon \let\emptystring\lambda -\def\bitsto{\mathbin{..}} -\turnradius{4pt} -\def\fixme{\marginpar{FIXME}} -\def\messages{% - \basedescript{% - \desclabelwidth{2.5cm}% - \desclabelstyle\pushlabel% - \let\makelabel\cookie% +\edef\Pr{\expandafter\noexpand\Pr\nolimits} +\newcommand{\bitsto}{\mathbin{..}} +\newcommand{\E}{{\mathcal{E}}} +\newcommand{\M}{{\mathcal{M}}} +\iffancystyle + \def\description{% + \basedescript{% + \let\makelabel\textit% + \desclabelstyle\multilinelabel% + \desclabelwidth{1in}% + }% + } +\fi +\def\fixme#1{\marginpar{FIXME}[FIXME: #1]} +\def\hex#1{\texttt{#1}_{x}} + +\newenvironment{longproof}[1]{% + \ifshort#1\expandafter\ignore + \else\proof\fi +}{% + \ifshort\else\endproof\fi +} + +\def\dbox#1{% + \vtop{% + \def\\{\unskip\egroup\hbox\bgroup\strut\ignorespaces}% + \hbox{\strut#1}% }% } -\let\endmessages\endbasedescript + +\def\Wident{\Xid{W}{ident}} +\def\Wkx{\Xid{W}{kx}} +\def\Wdkx{\Xid{W}{dkx}} +\def\Func#1#2{\mathcal{F}[#1\to#2]} +\def\diff#1#2{\Delta_{#1, #2}} +\def\Hid{H_{\textit{ID}}} + +%% protocol run diagrams +\def\PRaction#1{#1\ar[r]} +\def\PRcreatex#1{\PRaction{\textsf{Create session\space}#1}} +\def\PRcreate#1#2#3{\PRcreatex{(\text{#1},\text{#2},#3)}} +\def\PRreceivex#1{\PRaction{\textsf{Receive\space}#1}} +\def\PRreceive#1#2{\PRreceivex{\msg{#1}{#2}}} +\def\PRsession#1{\relax\mathstrut#1\ar[r]} +\def\msg#1#2{(\cookie{#1},#2)} +\def\PRresult#1{#1} +\def\PRsendx#1{\PRresult{\textsf{Send\space}#1}} +\def\PRsend#1#2{\PRsendx{\msg{#1}{#2}}} +\def\PRcomplete#1{\textsf{Complete:\space}#1} +\def\PRstate#1{\textsf{State:\space}#1} +\def\PRignore{\textsf{(ignored)}} +\def\PRreveal{\textsf{Session-state reveal}\ar[r]} +\def\protocolrun#1{\[\xymatrix @R=0pt @C=2em {#1}\]} + +\def\protocol{% + \unskip\bigskip + \begin{tabular*}{\linewidth}% + {@{\qquad}l@{\extracolsep{0ptplus1fil}}r@{\qquad}}} +\def\endprotocol{\end{tabular*}} +\def\send#1#2{\noalign{% + \centerline{\xy\ar @{#1}|*+{\mathstrut#2}<.5\linewidth, 0pt>\endxy}}} + +%% class-ids for proof of extractor lemma +\let\Cid=\Lambda +\let\Csession=S +\let\Cindex=r +\let\Cquery=Q +\let\Chash=H +\let\Ccheck=c +\let\Ccheckset=V +\let\Ccount=\nu + +\def\HG#1{\mathbf{H}_{#1}} + +\iffancystyle\else + \let\xsssec\subsubsection\def\subsubsection#1{\xsssec[#1]{#1.}} +\fi \begin{document} +%%%-------------------------------------------------------------------------- + \maketitle +\iffancystyle \thispagestyle{empty} \fi + \begin{abstract} - The Wrestlers Protocol\footnote{% - `The Wrestlers' is a pub in Cambridge which serves good beer and - excellent Thai food. It's where the authors made their first attempts at - a secure key-exchange protocol which doesn't use signatures.} % - is a key-exchange protocol with the interesting property that it leaves no - evidence which could be used to convince a third party that any of the - participants are involved. We describe the protocol and prove its security - in the random oracle model. - - Almost incidentally, we provide a new security proof for the CBC encryption - mode. Our proof is much simpler than that of \cite{Bellare:2000:CST}, and - gives a slightly better security bound. - - % I've not yet decided whose key-exchange model to use, but this ought to - % be mentioned. + We describe and prove (in the random-oracle model) the security of a simple + but efficient zero-knowledge identification scheme, whose security is based + on the computational Diffie-Hellman problem. Unlike other recent proposals + for efficient identification protocols, we don't need any additional + assumptions, such as the Knowledge of Exponent assumption. + + From this beginning, we build a simple key-exchange protocol, and prove + that it achieves `SK-security' -- and hence security in Canetti's Universal + Composability framework. + + Finally, we show how to turn the simple key-exchange protocol into a + slightly more complex one which provides a number of valuable `real-life' + properties, without damaging its security. \end{abstract} -\tableofcontents + +\iffancystyle \newpage +\thispagestyle{empty} +\columnsep=2em \columnseprule=0pt +\tableofcontents[\begin{multicols}{2}\raggedright][\end{multicols}] +%%\listoffigures[\begin{multicols}{2}\raggedright][\end{multicols}] +%% \listoftables[\begin{multicols}{2}\raggedright][\end{multicols}] +\newpage +\fi %%%-------------------------------------------------------------------------- \section{Introduction} -\label{sec:intro} -% Some waffle here about the desirability of a key-exchange protocol that -% doesn't leave signatures lying around, followed by an extended report of -% the various results. -%%%-------------------------------------------------------------------------- +This paper proposes protocols for \emph{identification} and +\emph{authenticated key-exchange}. + +An identification protocol allows one party, say Bob, to be sure that he's +really talking to another party, say Alice. It assumes that Bob has some way +of recognising Alice; for instance, he might know her public key. Our +protocol requires only two messages -- a challenge and a response -- and has +a number of useful properties. It is very similar to, though designed +independently of, a recent protocol by Stinson and Wu +\cite{cryptoeprint:2006:337}; we discuss their protocol and compare it to +ours in \ifshort the full version of this paper. \else +section~\ref{sec:stinson-ident}. \fi + +Identification protocols are typically less useful than they sound. As Shoup +\cite{cryptoeprint:1999:012} points out, it provides a `secure ping', by +which Bob can know that Alice is `there', but provides no guarantee that any +other communication was sent to or reached her. However, there are +situations where this an authentic channel between two entities -- e.g., a +device and a smartcard -- where a simple identification protocol can still be +useful. + +An authenticated key-exchange protocol lets Alice and Bob agree on a shared +secret, known to them alone, even if there is an enemy who can read and +intercept all of their messages, and substitute messages of her own. Once +they have agreed on their shared secret, of course, they can use standard +symmetric cryptography techniques to ensure the privacy and authenticity of +their messages. + + +\subsection{Desirable properties of our protocols} + +Our identification protocol has a number of desirable properties. +\begin{itemize} +\item It is \emph{simple} to understand and implement. In particular, it + requires only two messages. +\item It is fairly \emph{efficient}, requiring two scalar multiplications by + each of the prover and verifier. +\item It is provably \emph{secure} (in the random oracle model), assuming the + intractability of the computational Diffie-Hellman problem. +\end{itemize} -\section{Preliminaries} -\label{sec:prelim} -% Here we provide definitions of the various kinds of things we use and make, -% and describe some of the notation we use. +Our key-exchange protocol also has a number of desirable +properties. +\begin{itemize} +\item It is fairly \emph{simple} to understand and implement, though there + are a few subtleties. In particular, it is \emph{symmetrical}. We have + implemented a virtual private network system based on this protocol. +\item It is \emph{efficient}, requiring four scalar multiplications by each + participant. The communication can be reduced to three messages by + breaking the protocol's symmetry. +\item It is provably \emph{secure} (again, in the random oracle model), + assuming the intractability of the computational Diffie-Hellman problem, + and the security of a symmetric encryption scheme. +\item It provides \emph{perfect forward secrecy}. That is, even if a user's + long-term secrets are compromised, past sessions remain secure. +\item It is \emph{deniable}. It is possible to construct simulated + transcripts of protocol executions between any number of parties without + knowing any of their private keys. The simulated transcripts are (almost) + indistinguishable from real protocol transcripts. Hence, a transcript + does not provide useful evidence that a given party was really involved in + a given protocol execution. +\end{itemize} -\subsection{Bit strings} +\ifshort\else +\subsection{Asymptotic and concrete security results} + +Most security definitions for identification (particularly zero-knowledge) +and key-exchange in the literature are \emph{asymptotic}. That is, they +consider a family of related protocols, indexed by a \emph{security +parameter}~$k$; they that any \emph{polynomially-bounded} adversary has only +\emph{negligible} advantage. A polynomially-bounded adversary is one whose +running time is a bounded by some polynomial~$t(k)$. The security definition +requires that, for any such polynomially-bounded adversary, and any +polynomial $p(k)$, the adversary's advantage is less than $p(k)$ for all +sufficiently large values of $k$. + +Such asymptotic notions are theoretically interesting, and have obvious +connections to complexity theory. Unfortunately, such an asymptotic result +tells us nothing at all about the security of a particular instance of a +protocol, or what parameter sizes one needs to choose for a given level of +security against a particular kind of adversary. Koblitz and Menezes +\cite{cryptoeprint:2006:229} (among other useful observations) give examples +of protocols, proven to meet asymptotic notions of security, whose security +proofs guarantee nothing at all for the kinds of parameters typically used in +practice. + +Since, above all, we're interested in analysing a practical and implemented +protocol, we follow here the `practice-oriented provable security' approach +largely inspired by Bellare and Rogaway, and exemplified by +\cite{Bellare:1994:SCB,Bellare:1995:XMN,Bellare:1995:OAE,Bellare:1996:ESD,% +Bellare:1996:KHF,Bellare:1997:CST}; see also \cite{Bellare:1999:POP}. +Rather than attempting to say, formally, whether or not a protocol is +`secure', we associate with each protocol an `insecurity function' which +gives an upper bound on the advantage of any adversary attacking the protocol +within given resource bounds. +\fi -Most of our notation for bit strings is standard. The main thing to note is -that everything is zero-indexed. +\subsection{Formal models for key-exchange} -\begin{itemize} -\item We write $\Bin = \{0, 1\}$ for the set of binary digits. Then $\Bin^n$ - is the set of $n$-bit strings, and $\Bin^*$ is the set of all bit strings. -\item If $x$ is a bit string then $|x|$ is the length of $x$. If $x \in - \Bin^n$ then $|x| = n$. -\item If $x, y \in \Bin^n$ are strings of bits of the same length then $x - \xor y \in \Bin^n$ is their bitwise XOR. -\item If $x$ and $y$ are bit strings then $x \cat y$ is the result of - concatenating $y$ to $x$. If $z = x \cat y$ then we have $|z| = |x| + - |y|$. -\item The empty string is denoted $\emptystring$. We have $|\emptystring| = - 0$, and $x = x \cat \emptystring = \emptystring \cat x$ for all strings $x - \in \Bin^*$. -\item If $x$ is a bit string and $i$ is an integer satisfying $0 \le i < |x|$ - then $x[i]$ is the $i$th bit of $x$. If $a$ and $b$ are integers - satisfying $0 \le a \le b \le |x|$ then $x[a \bitsto b]$ is the substring - of $x$ beginning with bit $a$ and ending just \emph{before} bit $b$. We - have $|x[i]| = 1$ and $|x[a \bitsto b]| = b - a$; if $y = x[a \bitsto b]$ - then $y[i] = x[a + i]$. -\item If $x$ is a bit string and $n$ is a natural number then $x^n$ is the - result of concatenating $x$ to itself $n$ times. We have $x^0 = - \emptystring$ and if $n > 0$ then $x^n = x^{n-1} \cat x = x \cat x^{n-1}$. -\end{itemize} +\ifshort + +The first model for studying the \emph{computational} security of +key-exchange protocols (rather than using protocol-analysis logics like that +of \cite{Burrows:1989:LAa}) was given by Bellare and Rogaway +\cite{Bellare:1994:EAK}; the model has since been enhanced, both by the +original authors and others, in \cite{Bellare:1995:PSS,% +Blake-Wilson:1997:KAP,Blake-Wilson:1998:EAA}. The model defines security +in terms of a game: key-exchange protocols are secure if an adversary can't +distinguish the key agreed by a chosen `challenge session' from a key chosen +independently at random. Other models for key-exchange have been proposed in +\cite{Bellare:1998:MAD} and \cite{cryptoeprint:1999:012}; these use a +different notion of security, involving implementation of an ideal +functionality. -\subsection{Other notation} +\else + +Many proposed key-exchange protocols have turned out to have subtle security +flaws. The idea of using formal methods to analyse key-exchange protocols +begins with the logic of Burrows, Abadi and Needham \cite{Burrows:1989:LAa}. +Their approach requires a `formalising' step, in which one expresses in the +logic the contents of the message flows, and the \emph{beliefs} of the +participants. + +Bellare and Rogaway \cite{Bellare:1994:EAK} describe a model for studying the +computational security of authentication and key-exchange protocols in a +concurrent setting, i.e., where multiple parties are running several +instances of a protocol simultaneously. They define a notion of security in +this setting, and show that several simple protocols achieve this notion. +Their original paper dealt with pairs of parties using symmetric +cryptography; they extended their definitions in \cite{Bellare:1995:PSS} to +study three-party protocols involving a trusted key-distribution centre. + +Blake-Wilson, Johnson and Menezes \cite{Blake-Wilson:1997:KAP} applied the +model of \cite{Bellare:1994:EAK} to key-exchange protocols using asymmetric +cryptography, and Blake-Wilson and Menezes \cite{Blake-Wilson:1998:EAA} +applied it to protocols based on the Diffie-Hellman protocol. + +The security notion of \cite{Bellare:1994:EAK} is based on a \emph{game}, in +which an adversary nominates a \emph{challenge session}, and is given either +the key agreed by the participants of the challenge session, or a random +value independently sampled from an appropriate distribution. The +adversary's advantage -- and hence the insecurity of the protocol -- is +measured by its success probability in guessing whether the value it was +given is really the challenge key. This challenge-session notion was also +used by the subsequent papers described above. + +Bellare, Canetti and Krawczyk \cite{Bellare:1998:MAD} described a pair of +models which they called the \textsc{am} (for `authenticated links model') +and \textsc{um} (`unauthenticated links model'). They propose a modular +approach to the design of key-exchange protocols, whereby one first designs a +protocol and proves its security in the \textsc{am}, and then applies a +authenticating `compiler' to the protocol which they prove yields a protocol +secure in the realistic \textsc{um}. Their security notion is new. They +define an `ideal model', in which an adversary is limited to assigning +sessions fresh, random and unknown keys, or matching up one session with +another, so that both have the same key. They define a protocol to be secure +if, for any adversary~$A$ in the \textsc{am} or \textsc{um}, there is an +ideal adversary~$I$, such that the outputs of $A$ and $I$ are computationally +indistinguishable. + +In \cite{cryptoeprint:1999:012}, Shoup presents a new model for key-exchange, +also based on the idea of simulation. He analyses the previous models, +particularly \cite{Bellare:1994:EAK} and \cite{Bellare:1998:MAD}, and +highlights some of their inadequacies. +\fi + +Canetti and Krawczyk \cite{cryptoeprint:2001:040,Canetti:2001:AKE} describe a +new notion of security in the model of \cite{Bellare:1998:MAD}, based on the +challenge-session notion of \cite{Bellare:1994:EAK}. The security notion, +called `SK-security', seems weaker in various ways than those of earlier +works such as \cite{Bellare:1994:EAK} or \cite{cryptoeprint:1999:012}. +However, the authors show that their notion suffices for constructing `secure +channel' protocols, which they also define. + +\ifshort\else +In \cite{Canetti:2001:UCS}, Canetti describes the `universal composition' +framework. Here, security notions are simulation-based: one defines security +notions by presenting an `ideal functionality'. A protocol securely +implements a particular functionality if, for any adversary interacting with +parties who use the protocol, there is an adversary which interacts with +parties using the ideal functionality such that no `environment' can +distinguish the two. The environment is allowed to interact freely with the +adversary throughout, differentiating this approach from that of +\cite{Bellare:1998:MAD} and \cite{cryptoeprint:1999:012}, where the +distinguisher was given only transcripts of the adversary's interaction with +the parties. With security defined in this way, it's possible to prove a +`universal composition theorem': one can construct a protocol, based upon +various ideal functionalities, and then `plug in' secure implementations of +the ideal functionalities and appeal to the theorem to prove the security of +the entire protocol. The UC framework gives rise to very strong notions of +security, due to the interactive nature of the `environment' distinguisher. +\fi + +Canetti and Krawczyk \cite{Canetti:2002:UCN} show that the SK-security notion +of \cite{Canetti:2001:AKE} is \emph{equivalent} to a `relaxed' notion of +key-exchange security in the UC framework\ifshort\space of +\cite{Canetti:2001:UCS}\fi, and suffices for the construction of UC secure +channels. + +The result of \cite{Canetti:2002:UCN} gives us confidence that SK-security is +the `right' notion of security for key-exchange protocols. Accordingly, +SK-security is the standard against which we analyse our key-exchange +protocol. + + +\subsection{Outline of the paper} + +The remaining sections of this paper are as follows. \begin{itemize} -\item If $n$ is any natural number, then $\Nupto{n}$ is the set $\{\, i \in - \Z \mid 0 \le i < n \,\} = \{ 0, 1, \ldots, n \}$. -\item The symbol $\bot$ (`bottom') is different from every bit string and - group element. -\item We write $\Func{l}{L}$ as the set of all functions from $\Bin^l$ to - $\Bin^L$, and $\Perm{l}$ as the set of all permutations on $\Bin^l$. +\item Section \ref{sec:prelim} provides the essential groundwork for the rest + of the paper. It introduces important notation, and describes security + notions and intractability assumptions. +\item Section \ref{sec:zk-ident} describes our zero-knowledge identification + protocol and proves its security. +\item Section \ref{sec:kx} describes the simple version of our key-exchange + protocol, and proves its security and deniability. It also describes some + minor modifications which bring practical benefits without damaging + security. +\item Finally, section \ref{sec:conc} presents our conclusions. \end{itemize} -\subsection{Algorithm descriptions} +\ifshort +The full version of this paper describes how to make our protocols +identity-based by using bilinear pairings using the techniques introduced in +\cite{Boneh:2003:IBE}. It also contains proofs of the various theorems +stated here. +\fi + +%%%-------------------------------------------------------------------------- + +\section{Preliminaries} +\label{sec:prelim} -Most of the notation used in the algorithm descriptions should be obvious. -We briefly note a few features which may be unfamiliar. +\ifshort +\subsection{Basics} +\let\prelimsec\subsubsection +\else +\let\prelimsec\subsection +\fi + +\prelimsec{Miscellaneous notation} + +We write $\Func{D}{R}$ for the set of all functions with domain $D$ and range +$R$. + +\prelimsec{Groups} + +Let $(G, +)$ be a cyclic group\footnote{ + We find that additive group notation is easier to read. In particular, in + multiplicative groups, one ends up with many interesting things tucked away + in little superscripts.}% +of prime order $q$, and generated by an element $P$. We shall write the +identity of $G$ as $0_G$, or simply as $0$ when no ambiguity is likely to +arise. Thus, we have $\langle P \rangle = G$ and $q P = 0$. Any $X \in G$ +can be written as $X = x P$ for some $x \in \{0, 1, \ldots, q - 1\}$. + +We consider a cyclic group of order $n$ as a $\Z/n\Z$-module, and in +particular our group $G$ can be seen as a vector space over $\gf{q}$. This +makes the notation slightly more convenient. + +\prelimsec{Bit strings and encodings} +\label{sec:bitenc} + +Let $\Bin = \{0, 1\}$ be the set of binary digits. Then $\Bin^n$ is the set +of $n$-bit strings, and $\Bin^*$ the set of all (finite) bit strings. If $x +\in \Bin^n$ is a bit string, we write its length as $|x| = n$. For a bit +string $x \in \Bin^n$, and for $0 \le i < n$, we write $x[i]$ as the $i$th +bit of $x$. The empty string is denoted $\emptystring$. + +Let $x$ and $y$ be two bit strings. If $|x| = |y| = n$, we write $x \xor y$ +to mean the bitwise exclusive-or of $x$ and $y$\ifshort\else: if $z = x \xor +y$ then $|z| = n$, and $z[i] = (x[i] + y[i]) \bmod 2$ for $0 \le i < n$\fi. +We write $x \cat y$ to mean the concatenation of $x$ and $y$\ifshort\else: if +$z = x \cat y$ then $|z| = |x| + |y|$ and $z[i] = x[i]$ if $0 \le i < |x|$ +and $z[i] = y[i - |x|]$ if $|x| < i \le |x| + |y|$\fi. + +Finally, we let $\bot$ be a value distinct from any bit string. + +We shall want to encode group elements $X \in G$ and indices $x \in I = +\gf{q}$ as bit strings. +\ifshort +To this end, we shall assume the existence of efficient, unambiguous +encodings of group elements as $\ell_G$-bit strings, and indices as +$\ell_I$-bit strings. To reduce clutter, we shall leave encoding and +decoding as implicit operations. +\else +To this end, we shall assume the existence of +integers $\ell_G, \ell_I > 0$ and functions +\[ + e_S\colon S \to \Bin^{\ell_S} + \quad \textrm{and} \quad + d_S\colon \Bin^{\ell_S} \to S \cup \{ \bot \} + \qquad + \textrm{for } S \in \{ G, \F \}. +\] +with the following properties. \begin{itemize} -\item The notation $a \gets x$ denotes the action of assigning the value $x$ - to the variable $a$. -\item The notation $a \getsr X$, where $X$ is a finite set, denotes the - action of assigning to $a$ a random value $x \in X$ according to the - uniform probability distribution on $X$; i.e., following $a \getsr X$, - $\Pr[a = x] = 1/|X|$ for any $x \in X$. +\item The functions are \emph{unique} and \emph{unambiguous}, i.e., for any + $t \in \Bin^{\ell_S}$, we have + \[ d_S(t) = \begin{cases} + s & if there is some $s \in S$ such that $t = e_S(s)$, or \\ + \bot & if no such $s$ exists. + \end{cases} + \] +\item The functions should be \emph{efficient} to compute. Indeed, we shall + be assuming that the time taken for encoding and decoding is essentially + trivial. \end{itemize} -The notation is generally quite sloppy about types and scopes. In -particular, there are implicit coercions between bit strings, integers and -group elements. Any simple injective mapping will do for handling the -conversions. We don't think these informalities cause much confusion, and -they greatly simplify the presentation of the algorithms. - -\subsection{Random oracles} - -We shall analyse the Wrestlers Protocol in the random oracle model -\cite{Bellare:1993:ROP}. That is, each participant including the adversary -is given oracle access (only) to a uniformly-distributed random function -$H\colon \Bin^* \to \Bin^\infty$ chosen at the beginning of the game: for any -input string $x$, the oracle can produce, on demand, any prefix of an -infinitely long random answer $y = H(x)$. Repeating a query yields a prefix -of the same random result string; asking a new query yields a prefix of a new -randomly-chosen string. - -We shan't need either to query the oracle on very long input strings nor -shall we need outputs much longer than a representation of a group index. -Indeed, since all the programs we shall be dealing with run in finite time, -and can therefore make only a finite number of oracle queries, each with a -finitely long result, we can safely think about the random oracle as a finite -object. - -Finally, we shall treat the oracle as a function of multiple inputs and -expect it to operate on some unambiguous encoding of all of the arguments in -order. - -\subsection{Symmetric encryption} - -\begin{definition}[Symmetric encryption] - \label{def:sym-enc} - A \emph{symmetric encryption scheme} $\mathcal{E} = (E, D)$ is a pair of - algorithms: - \begin{itemize} - \item a randomized \emph{encryption algorithm} $E\colon \keys \mathcal{E} - \times \Bin^* \to \Bin^*$; and - \item a deterministic \emph{decryption algorithm} $E\colon \keys - \mathcal{E} \times \Bin^* \to \Bin^* \cup \{ \bot \}$ - \end{itemize} - with the property that, for any $K \in \keys \mathcal{E}$, any plaintext - message $x$, and any ciphertext $y$ returned as a result of $E_K(x)$, we - have $D_K(y) = x$. +Note that, as we have defined them, all encodings of group elements are the +same length, and similarly for encodings of indices. This is necessary for +the security of our protocols. + +We shall frequently abuse notation by omitting the encoding and decoding +functions where it is obvious that they are required. +\fi + +\ifshort\else +\prelimsec{Games, adversaries, and oracles} +\label{sec:games} + +Many of the security definitions and results given here make use of +\emph{games}, played with an \emph{adversary}. An adversary is a +probabilistic algorithm. In some games, the adversary is additionally +equipped with \emph{oracles}, which perform computations with values chosen +by the adversary and secrets chosen by the game but not revealed to the +adversary. We impose limits on the adversary's resource usage: in +particular, the total time it takes, and the number of queries it makes to +its various oracles. Throughout, we include the size of the adversary's +program as part of its `time', in order to model adversaries which contain +large precomputed tables. + +The games provide models of someone trying to attack a construction or +protocol. For security, we will either define a notion of `winning' the +game, and require that all adversaries have only a very small probability of +winning, or we consider two different games and require that no adversary can +distinguish between the two except with very small probability. + +Our proofs make frequent use of sequences of games; see +\cite{cryptoeprint:2004:332,cryptoeprint:2004:331}. The presentation owes +much to Shoup \cite{cryptoeprint:2004:332}. We begin with a game $\G0$ based +directly on a relevant security definition, and construct a sequence of games +$\G1$, $\G2$, \dots, each slightly different from the last. We define all of +the games in a sequence over the same underlying probability space -- the +random coins tossed by the algorithms involved -- though different games may +have slightly differently-defined events and random variables. Our goal in +doing this is to bound the probability of the adversary winning the initial +game $\G0$ by simultaneously (a) relating the probability of this event to +that of corresponding events in subsequent games, and (b) simplifying the +game until the probability of the corresponding event can be computed +directly. + +The following simple lemma from \cite{Shoup:2001:OR} will be frequently +useful. +\begin{lemma}[Difference Lemma] + \label{lem:shoup} + Let $S$, $T$, $F$ be events. Suppose $\Pr[S \mid \bar F] = + \Pr[T \mid \bar F]$. Then $|\Pr[S] - \Pr[T]| \le \Pr[F]$. +\end{lemma} +\begin{proof} + A simple calculation: + \begin{eqnarray*}[rl] + |\Pr[S] - \Pr[T]| + & = |(\Pr[S \mid F]\Pr[F] + \Pr[S \mid \bar F]\Pr[\bar F]) - + (\Pr[T \mid F]\Pr[F] + \Pr[T \mid \bar F]\Pr[\bar F])| \\ + & = \Pr[F] \cdot |\Pr[S \mid F] - \Pr[T \mid F]| \\ + & \le \Pr[F] + \end{eqnarray*} + and we're done! +\end{proof} +\fi + + +\prelimsec{The random oracle model} +\label{sec:ro} + +\ifshort\else +In particular, most of our results will make use of the \emph{random oracle} +model \cite{Bellare:1993:ROP}, in which all the participants, including the +adversary, have access to a number of `random oracles'. A random oracle with +domain $D$ and range $R$ is an oracle which computes a function chosen +uniformly at random from the set of all such functions. (In the original +paper \cite{Bellare:1993:ROP}, random oracles are considered having domain +$\Bin^*$ and range $\Bin^\omega$; we use finite random oracles here, because +they're easier to work with.) + +Given a protocol proven secure in the random oracle model, we can instantiate +each random oracle by a supposedly-secure hash function and be fairly +confident that either our protocol will be similarly secure, or one of the +hash functions we chose has some unfortunate property. + +Proofs in the random oracle must be interpreted carefully. For example, +Canetti, Goldreich and Halevi \cite{Canetti:2004:ROM} show that there are +schemes which can be proven secure in the random oracle model but provably +have no secure instantiation in the standard model. +\fi + +The random oracle model \ifshort\cite{Bellare:1993:ROP} \fi is useful for +constructing reductions and simulators for two main reasons. +\begin{enumerate} +\item One can use the transcript of an adversary's queries to random oracles + in order to extract knowledge from it. +\item One can `program' a random oracle so as to avoid being bound by prior + `commitments', or to guide an adversary towards solving a selected instance + of some problem. +\end{enumerate} +Our proofs only make use of the first feature. This becomes particularly +important when we consider issues of zero-knowledge and deniability in a +concurrent setting, because we want to be able to claim that we retain these +features when the random oracle is instantiated using a cryptographic hash +function, and hash functions definitely aren't `programmable' in this way! +The former property seems rather more defensible -- one would indeed hope +that the only sensible way of working out (anything about) the hash of a +particular string is to actually compute the hash function, and the random +oracle model is, we hope, just giving us a `hook' into this process. + +\ifshort\else +(Our protocols can be modified to make use of bilinear pairings so as to +provide identity-based identification and key-exchange, using the techniques +of \cite{Boneh:2003:IBE}. Proving the security of the modifications we +discuss would involve `programming' random oracles, but this doesn't affect +the zero-knowledge or deniability of the resulting protocols.) +\fi + + +\ifshort\else +\prelimsec{Notation for algorithms} + +We shall have occasion to describe algorithms by means of a pseudocode. Our +choice of pseudocode is unlikely to be particularly controversial. We let $x +\gets y$ denote the action of setting $x$ to the value $y$; similarly, $x +\getsr Y$ denotes the action of sampling $x$ from the set $Y$ uniformly at +random. + +The expression $a \gets A^{O(\cdot, x)}(y)$ means `assign to $a$ the value +output by algorithm $A$ on input $y$, and with oracle access to the algorithm +which, given input $z$, computes $O(z, x)$'. + +We make use of conditional (\IF-\ELSE) and looping (\FOR-\DO and \WHILE-\DO) +constructions; in order to reduce the amount of space taken up, the bodies of +such constructions are shown by indentation only. + +We don't declare the types of our variables explicitly, assuming that these +will be obvious by inspection; also, we don't describe our variables' scopes +explicitly, leaving the reader to determine these from context. + +Finally, the notation $\Pr[\textit{algorithm} : \textit{condition}]$ denotes +the probability that \textit{condition} is true after running the given +\textit{algorithm}. +\fi + +\prelimsec{Diffie-Hellman problems} +\label{sec:dhp} + +The security of our protocols is related to the hardness of the +computational, decisional, and gap Diffie-Hellman problems in the group $G$. +We define these problems and what it means for them to be `hard' here. + +The \emph{computational} Diffie-Hellman problem (CDH) is as follows: given +two group elements $X = x P$ and $Y = y P$, find $Z = x y P$. +\ifshort\else +\begin{definition}[The computational Diffie-Hellman problem] + Let $(G, +)$ be a cyclic group generated by $P$. For any adversary $A$, we + say that $A$'s \emph{success probability} at solving the computational + Diffie-Hellman problem in $G$ is + \[ \Succ{cdh}{G}(A) = + \Pr[ x \getsr I; y \getsr \Z/\#G\Z : A(x P, y P) = x y P ] + \] + where the probability is taken over the random choices of $x$ and $y$ and + any random decisions made by $A$. We say that the \emph{CDH insecurity + function} of $G$ is + \[ \InSec{cdh}(G; t) = \max_A \Succ{cdh}{G}(A) \] + where the maximum is taken over adversaries which complete in time $t$. \end{definition} +Certainly, if one can compute discrete logarithms in the group $G$ (i.e., +given $x P$, find $x$), then one can solve the computational Diffie-Hellman +problem. The converse is not clear, though. Shoup \cite{Shoup:1997:LBD} +gives us some confidence in the difficulty of the problem by showing that a +\emph{generic} adversary -- i.e., one which makes no use of the specific +structure of a group -- has success probability no greater than $q^2/\#G$. + +This isn't quite sufficient for our purposes. Our proofs will be able to +come up with (possibly) a large number of guesses for the correct answer, and +at most one of them will be correct. Unfortunately, working out which one is +right seems, in general, to be difficult. This is the \emph{decision} +Diffie-Hellman problem (DDH), which \cite{Shoup:1997:LBD} shows, in the +generic group model, is about as hard as CDH. (See \cite{Boneh:1998:DDP} for +a survey of the decision Diffie-Hellman problem.) +\par\fi +Our reference problem will be a `multiple-guess computational Diffie-Hellman +problem' (MCDH), which is captured by a game as follows. An adversary is +given a pair of group elements $(x P, y P)$, and an oracle $V(\cdot)$ which +accepts group elements as input. The adversary wins the game if it queries +$V(x y P)$. -\begin{definition}[Chosen plaintext security for symmetric encryption] - \label{def:sym-cpa} - Let $\mathcal{E} = (E, D)$ be a symmetric encryption scheme. Let $A$ be - any algorithm. Define +\begin{figure} \begin{program} - Experiment $\Expt{lor-cpa-$b$}{\mathcal{E}}(A)$: \+ \\ - $K \getsr \keys \mathcal{E}$; \\ - $b' \getsr A^{E_K(\id{lr}(b, \cdot, \cdot))}$; \\ - \RETURN $b'$; + $\Game{mcdh}{G}(A)$: \+ \\ + $w \gets 0$; \\ + $x \getsr \Z/\#G\Z$; $y \getsr \Z/\#G\Z$; \\ + $A^{V(\cdot)}(x P, y P)$; \\ + \RETURN $w$; \next - Function $\id{lr}(b, x_0, x_1)$: \+ \\ - \RETURN $x_b$; + Function $V(Z)$: \+ \\ + \IF $Z = x y P$ \THEN \\ \ind + $w \gets 1$; \\ + \RETURN $1$; \- \\ + \RETURN $0$; \end{program} - An adversary $A$ is forbidden from querying its encryption oracle - $E_K(\id{lr}(b, \cdot, \cdot))$ on a pair of strings with differing - lengths. We define the adversary's \emph{advantage} in this game by - \begin{equation} - \Adv{lor-cpa}{\mathcal{E}}(A) = - \Pr[\Expt{lor-cpa-$1$}{\mathcal{E}}(A) = 1] - - \Pr[\Expt{lor-cpa-$0$}{\mathcal{E}}(A) = 1] - \end{equation} - and the \emph{left-or-right insecurity of $\mathcal{E}$ under - chosen-plaintext attack} is given by - \begin{equation} - \InSec{lor-cpa}(\mathcal{E}; t, q_E, \mu_E) = - \max_A \Adv{lor-cpa}{\mathcal{E}}(A) - \end{equation} - where the maximum is taken over all adversaries $A$ running in time $t$ and - making at most $q_E$ encryption queries, totalling most $\mu_E$ bits of - plaintext. + + \caption{The multiple-guess computational Diffie-Hellman problem: + $\Game{mcdh}{G}(A)$} + \label{fig:mcdh} +\end{figure} + +\begin{definition}[The multiple-guess computational Diffie-Hellman problem] + \label{def:mcdh} + Let $(G, +)$ be a cyclic group generated by $P$. For some adversary $A$, + we say that $A$'s \emph{success probability} at solving the multiple-guess + computational Diffie-Hellman problem in $G$ is + \[ \Succ{mcdh}{G}(A) = \Pr[\Game{mcdh}{G}(A) = 1] \] + where $\Game{mcdh}{G}(A)$ is shown in figure~\ref{fig:mcdh}. We say that + the \emph{MCDH insecurity function of $G$} is + \[ \InSec{mcdh}(G; t, q_V) = \max_A \Succ{mcdh}{G}(A) \] + where the maximum is taken over adversaries which complete in time $t$ and + make at most $q_V$-oracle queries. \end{definition} +\ifshort +We can (loosely) relate the difficulty of MCDH to the difficulty of +the standard CDH problem, in which the adversary is allowed only a single +guess. +\else +Note that our MCDH problem is not quite the `gap Diffie-Hellman problem' +(GDH). The gap problem measures the intractibility of solving CDH even with +the assistance of an oracle for solving (restricted) decision Diffie-Hellman +problems in the group. Specifically, the adversary is given $(X, Y) = (x P, +y P)$ and tries to find $Z = x y P$, as for CDH, but now it has access to an +oracle $D(R, S)$ which answers $1$ if $S = x R$ and $0$ otherwise. + +Clearly MCDH is at least as hard as GDH, since our simple verification oracle +$V(Z)$ can be simulated with the gap problem's DDH oracle, as $D(Y, Z)$. +However, we can (loosely) relate the difficulty of MCDH to the difficulty of +CDH. +\fi +\begin{proposition}[Comparison of MCDH and CDH security] + For any cyclic group $(G, +)$, + \[ \InSec{mcdh}(G; t, q_V) \le + \ifshort q_V\,\InSec{mcdh}(G; t + O(q_V), 1) \else + q_V\,\InSec{cdh}(G; t + O(q_V)) \fi. + \] +\end{proposition} +\begin{longproof}{The proof of this proposition may be found in the full + version of this paper.} + Let $A$ be an adversary attacking the multiple-guess computational + Diffie-Hellman problem in $G$, and suppose that it runs in time $t$ and + issues $q_V$ queries to its verification oracle. + + We use a sequence of games. Game $\G0$ is the original MCDH attack game. + In each game $\G{i}$, we let the event $S_i$ be the probability that the + adversary wins the game. + + Game $\G1$ is the same as $\G0$, except that we change the behaviour of the + verification oracle. Specifically, we make the oracle always return $0$. + We claim that this doesn't affect the adversary's probability of winning, + i.e., $\Pr[S_1] = \Pr[S_0]$. To see this, note that if none of the + adversary's $V(\cdot)$ queries was correct, then there is no change in the + game; conversely, if any query was correct, then the adversary will have + won regardless of its subsequent behaviour (which may differ arbitrarily + between the two games). + + We are now ready to construct from $A$ an adversary $B$ attacking the + standard computational Diffie-Hellman problem. + \begin{program} + Adversary $B(X, Y)$: \+ \\ + $n \gets 0$; \\ + \FOR $i \in \Nupto{q_V}$ \DO $Q_i \gets 0$; \\ + $A^{V(\cdot)}$; \\ + $r \getsr \Nupto{n}$; \\ + \RETURN $Q_r$; + \next + Function $D(Z')$: \+ \\ + $Q_n \gets Z'$; \\ + $n \gets n + 1$; \\ + \RETURN $0$; + \end{program} + Observe that $B$ provides $A$ with an accurate simulation of game $\G1$. + Moreover, at the end of the algorithm, we have $0 < n \le q_V$, and the + values $Q_0$, $Q_1$, \dots, $Q_{n-1}$ are the values of $A$'s oracle + queries. Hence, with probability $Pr[S_1]$, at least of one of the $Q_i$ + is the correct answer to the CDH problem. Let $\epsilon = \Pr[S_1] = + \Pr[S_0]$; we claim that $B$'s probability of success is at least + $\epsilon/q_V$. The proposition follows directly from this claim and that, + because $A$ was chosen arbitrarily, we can maximize and count resources. + + We now prove the above claim. For $0 \le i < q_V$, let $W_i$ be the + event that $Q_i = x y P$, i.e., that $Q_i$ is the correct response. A + simple union bound shows that + \[ \sum_{0\le i p$, we can encode $n$ as $e(p, +\ell_G, n)$, as above. + +Alternatively, let $\F = \gf{p^f}$ be a finite field, and $E$ be an elliptic +curve defined over $\F$ such that the group $E(\F)$ of $\F$-rational points +of $E$ has a prime-order cyclic subgroup $G$. Elements of $G$ can be +represented as pairs of elements of $\F$. If $f = 1$, i.e., $\F = \Z/p\Z$ +then field elements can be encoded as above. If $p = 2$, we can represent +the field as $\F_2/(p(x))$ for some irreducible polynomial $p(x) \in \F_2[x]$ +of degree $f$. An element $r \in \F$ can then be represented by a polynomial +$r(x)$ with degree less than $f$, and coefficients $c_i \in \{0, 1\}$, i.e., +\[ r(x) = \sum_{0\le i: <0cm, 1.5cm>::} - *++[F:<4pt>]\txt{\ns Start \\ Choose $\rho_A$} ="start" - :[dd] - *++[F:<4pt>]\txt{ - \ns State \c{challenge} \\ - Send $(\c{pre-challenge}, r_A)$} - ="chal" - [] "chal" !{!L(0.5)} ="chal-cookie" - :@(d, d)[l] - *+\txt{Send $(\c{cookie}, r_A, c_B)$} - ="cookie" - |*+\txt{Receive \\ $(\c{pre-challenge}, r_B)$ \\ (no spare slot)} - :@(u, u)"chal-cookie" - "chal" :@/_0.8cm/ [ddddl] - *+\txt{Send \\ $(\c{challenge}, $\\$ r_A, c_B, v_A)$} - ="send-chal" - |<>(0.67) *+\txt\small{ - Receive \\ $(\c{pre-challenge}, r_B)$ \\ (spare slot)} - "chal" :@/^0.8cm/ "send-chal" |<>(0.33) - *+\txt{Receive \\ $(\c{cookie}, r_B, c_A)$} - :[rr] - *+\txt{Send \\ $(\c{reply}, c_A, c_B, $\\$ v_A, E_K(r_B^\alpha))$} - ="send-reply" - |*+\txt{Receive \\ $(\c{challenge}, $\\$ r_B, c_A, v_B)$} - "chal" :"send-reply" - |*+\txt{Receive \\ $(\c{challenge}, $\\$ r_B, c_A, v_B)$} - "send-chal" :[ddd] - *++[F:<4pt>]\txt{ - \ns State \c{commit} \\ - Send \\ $(\c{switch}, c_A, c_B, $\\$ E_K(r_B^\alpha, w_A))$} - ="commit" - |*+\txt{Receive \\ $(\c{reply}, c_B, c_A, $\\$ v_B, E_K(b^{\rho_A}))$} - :[rr] - *+\txt{Send \\ $(\c{switch-ok}, E_K(u_A))$} - ="send-switch-ok" - |*+\txt{Receive \\ $(\c{switch}, c_B, c_A, $\\$ E_K(b^{\rho_A}, w_B))$} - "send-reply" :"commit" - |*+\txt{Receive \\ $(\c{reply}, c_B, c_A, $\\$ v_B, E_K(b^{\rho_A}))$} - "send-reply" :"send-switch-ok" - |*+\txt{Receive \\ $(\c{switch}, c_B, c_A, $\\$ E_K(b^{\rho_A}, w_B))$} - :[dddl] - *++[F:<4pt>]\txt{\ns Done} - ="done" - "commit" :"done" - |*+\txt{Receive \\ $(\c{switch-ok}, E_K(u_B))$} - "send-chal" [r] !{+<0cm, 0.75cm>} - *\txt\itshape{For each outstanding challenge} - ="for-each" - !{"send-chal"+DL-<8pt, 8pt> ="p0", - "for-each"+U+<8pt> ="p1", - "send-reply"+UR+<8pt, 8pt> ="p2", - "send-reply"+DR+<8pt, 8pt> ="p3", - "p0" !{"p1"-"p0"} !{"p2"-"p1"} !{"p3"-"p2"} - *\frm<8pt>{--}} - \end{graph} \] - - \caption{State-transition diagram for key-exchange protocol} - \label{fig:kx-states} + \begin{description} + \item[Setup] Group $G = \langle P \rangle$; $\#G = q$ is prime. + $H_I(\cdot, \cdot)$ is a secure hash. + \item[Private key] $x \inr \gf{q}$. + \item[Public key] $X = x P$. + \item[Challenge] $(R, c)$ where $r \inr \gf{q}$, $R = r P$, $c = r \xor + H_I(R, r X)$. + \item[Response] $x R = r X$ if $R = (c \xor H_I(R, x R)) P$; otherwise + $\bot$. + \end{description} + + \caption{Summary of the Wrestlers Identification Protocol, $\Wident$} + \label{fig:wident} \end{figure} -We now describe the protocol message by message, and Alice's actions when she -receives each. Since the protocol is completely symmetrical, Bob should do -the same, only swapping round $A$ and $B$ subscripts, the public keys $a$ and -$b$, and using his private key $\beta$ instead of $\alpha$. -\subsubsection{Starting the protocol} +\subsection{Security} -As described above, at the beginning of the protocol Alice chooses a random -$\rho_A \inr \Nupto q$, and computes her \emph{challenge} $r_A = g^{\rho_A}$ -and her \emph{cookie} $c_A = H(\cookie{cookie}, r_A)$. She sends her -announcement of her challenge as -\begin{equation} - \label{eq:kx-pre-challenge} - \cookie{kx-pre-challenge}, r_A -\end{equation} -and enters the \cookie{challenge} state. - -\subsubsection{The \cookie{kx-pre-challenge} message} +In order to evaluate the security of our protocol, we present a formal +description of the algorithms involved in figure~\ref{fig:wident}. Here, the +hash function $H_I(\cdot, \cdot)$ is modelled as a random oracle. -If Alice receieves a \cookie{kx-pre-challenge}, she ensures that she's in the -\cookie{challenge} state: if not, she rejects the message. +\begin{figure} + \begin{program} + Function $\id{setup}()$: \+ \\ + $x \getsr \gf{q}$; \\ + $X \gets x P$; \\ + \RETURN $(x, X)$; + \ifshort\newline\else\next\fi + Function $\id{challenge}^{H_I(\cdot, \cdot)}(R, c, X)$: \+ \\ + $r \getsr \gf{q}$; \\ + $R \gets r P$; $Y \gets r X$; \\ + $h \gets H_I(R, Y)$; $c \gets r \xor h$; \\ + \RETURN $(Y, R, c)$; \- \\[\medskipamount] + Function $\id{verify}(Y, Y')$: \+ \\ + \IF $Y' = Y$ \THEN \RETURN $1$; \\ + \RETURN $0$; + \next + Function $\id{response}^{H_I(\cdot, \cdot)}(R, c, x)$: \+ \\ + $Y' \gets x R$; \\ + $h \gets H_I(R', Y')$; $r' \gets c \xor h$; \\ + \IF $R \ne r' P$ \THEN \RETURN $\bot$; \\ + \RETURN $Y'$; + \end{program} -She must first calculate Bob's cookie $c_B = H(\cookie{cookie}, r_B)$. Then -she has a choice: either she can send a full challenge, or she can send the -cookie back. + \caption{Functions implementing $\Wident$ in the random oracle model} + \label{fig:wident-ro} +\end{figure} -Suppose she decides to send a full challenge. She must compute a \emph{check -value} -\begin{equation} - \label{eq:v_A} - v_A = \rho_A \xor H(\cookie{expected-reply}, r_A, r_B, b^{\rho_A}) -\end{equation} -and sends -\begin{equation} - \label{eq:kx-challenge} - \cookie{kx-challenge}, r_A, c_B, v_A -\end{equation} -to Bob. Then she remembers Bob's challenge for later use, and awaits his -reply. +\subsubsection{Completeness} +Suppose that Bob really is talking to Alice. Note that $Y' = x R = x (r P) = +r (x P) = r X = Y$. Hence $r' = c \xor H_I(R', Y') = c \xor H_I(R, Y) = r$, +so $r' P = r P = R$, so Alice returns $Y' = Y$ to Bob. Therefore $\Wident$ +is \emph{complete}: if Bob really is communicating with Alice then he +accepts. + +\subsubsection{Soundness} +We next show that impersonating Alice is difficult. The natural way to prove +this would be to give an adversary a challenge and prove that its probability +of giving a correct response is very small. However, we prove a stronger +result: we show that if the adversary can respond correctly to any of a large +collection of challenges then it can solve the MCDH problem. + +Consider the game $\Game{imp}{\Wident}$ shown in +figure~\ref{fig:wident-sound}. An adversary's probability of successfully +impersonating Alice in our protocol, by correctly responding to any one of +$n$ challenges, is exactly its probability of winning the game (i.e., causing +it to return $1$). -If she decides to send only a cookie, she just transmits -\begin{equation} - \label{eq:kx-cookie} - \cookie{kx-cookie}, r_A, c_B -\end{equation} -to Bob and forgets all about it. - -Why's this useful? Well, if Alice sends off a full \cookie{kx-challenge} -message, she must remember Bob's $r_B$ so she can check his reply and that -involves using up a table slot. That means that someone can send Alice -messages purporting to come from Bob which will chew up Alice's memory, and -they don't even need to be able to read Alice's messages to Bob to do that. -If this protocol were used over the open Internet, script kiddies from all -over the world might be flooding Alice with bogus \cookie{kx-pre-challenge} -messages and she'd never get around to talking to Bob. - -By sending a cookie intead, she avoids committing a table slot until Bob (or -someone) sends either a cookie or a full challenge, thus proving, at least, -that he can read her messages. This is the best we can do at this stage in -the protocol. Against an adversary as powerful as the one we present in -section~\fixme\ref{sec:formal} this measure provides no benefit (but we have -to analyse it anyway); but it raises the bar too sufficiently high to -eliminate a large class of `nuisance' attacks in the real world. - -Our definition of the Wrestlers Protocol doesn't stipulate when Alice should -send a full challenge or just a cookie: we leave this up to individual -implementations, because it makes no difference to the security of the -protocol against powerful adversaries. But we recommend that Alice proceed -`optimistically' at first, sending full challenges until her challenge table -looks like it's running out, and then generating cookies only if it actually -looks like she's under attack. This is what our pseudocode in -figure~\ref{fig:kx-messages} does. - -\subsubsection{The \cookie{kx-cookie} message} - -When Alice receives a \cookie{kx-cookie} message, she must ensure that she's -in the \cookie{challenge} state: if not, she rejects the message. She checks -the cookie in the message against the value of $c_A$ she computed earlier. -If all is well, Alice sends a \cookie{kx-challenge} message, as in -equation~\ref{eq:kx-challenge} above. - -This time, she doesn't have a choice about using up a table slot to remember -Bob's $r_B$. If her table size is fixed, she must choose a slot to recycle. -We suggest simply recycling slots at random: this means there's no clever -pattern of \cookie{kx-cookie} messages an attacker might be able to send to -clog up all of Alice's slots. - -\subsubsection{The \cookie{kx-challenge} message} +\begin{figure} + \begin{program} + $\Game{imp-$n$}{\Wident}(A)$: \+ \\ + $H_I \getsr \Func{G^2}{\Bin^{\ell_I}}$; \\ + $(x, X) \gets \id{setup}()$; \\ + $\id{win} \gets 0$; \\ + $\Xid{R}{map} \gets \emptyset$; \\ + $\mathbf{c} \gets \id{challenges}(n)$; \\ + $(R', Y') \gets A^{H_I(\cdot, \cdot), \id{check}(\cdot, \cdot)} + (X, \mathbf{c})$; \\ + \RETURN $\id{win}$; + \newline + Function $\id{challenges}(n)$: \+ \\ + \FOR $i \in \Nupto{n}$ \DO \\ \ind + $(Y, R, c) \gets \id{challenge}^{H_I(\cdot, \cdot)}$; \\ + $\Xid{R}{map} \gets \Xid{R}{map} \cup \{ R \mapsto Y \}$; \\ + $\mathbf{c}[i] \gets (R, c)$; \- \\ + \RETURN $\mathbf{c}$; \next + Function $\id{check}(R', Y')$: \\ + \IF $R' \notin \dom \Xid{R}{map}$ \THEN \RETURN $0$; \\ + $Y \gets \Xid{R}{map}(R')$; \\ + \IF $\id{verify}(Y, Y')$ \THEN \\ \ind + $\id{win} \gets 1$; \\ + \RETURN $1$; \- \\ + \RETURN $0$; + \end{program} + \caption{Soundness of $\Wident$: $\Game{imp-$n$}{\Wident}(A)$} + \label{fig:wident-sound} +\end{figure} +\begin{theorem}[Soundness of $\Wident$] + \label{thm:wident-sound} + Let $A$ be any adversary running in time $t$ and making $q_I$ queries to + its random oracle, and $q_V$ queries to its verification oracle. Let $G$ + be a cyclic group. Then + \[ \Pr[\Game{imp-$n$}{\Wident^G}(A) = 1] \le + \InSec{mcdh}(G; t', q_I + q_V) + \] + where $t' = t + O(q_I) + O(q_V)$. +\end{theorem} +\begin{remark} + Note that the security bound here is \emph{independent} of the value of + $n$. +\end{remark} +\begin{longproof}{The proof of this theorem can be found in the full version + of the paper.} + We prove this by defining a sequence of games $\G{i}$. The first will be + the same as the attack game $\Game{imp-$n$}{\Wident}(A)$ and the others + will differ from it in minor ways. In each game $\G{i}$, let $S_i$ be the + event that $A$ wins the game -- i.e., that it successfully impersonates the + holder of the private key~$x$. + + Let game $\G0$ be the attack game $\Game{imp}{\Wident}(A)$, and let $(R', + Y')$ be the output of $A$ in the game. + + We define a new game $\G1$ which is the same as $\G0$, except that we query + the random oracle $H_I$ at $(R', Y')$ whenever the adversary queries + $\id{check}(R', Y')$. (We don't charge the adversary for this.) This + obviously doesn't affect the adversary's probability of winning, so + $\Pr[S_1] = \Pr[S_0]$. + + Game $\G2$ is like $\G1$, except that we change the way we generate + challenges and check their responses. Specifically, we new functions + $\id{challenges}_2$ and $\id{check}_2$, as shown in + figure~\ref{fig:wident-sound-2}. + + \begin{figure} + \begin{program} + Function $\id{challenges}_2(n)$: \+ \\ + $r^* \getsr I$; $R^* \gets r^* P$; $Y^* \gets r^* X$; \\ + \FOR $i \in \Nupto{n}$ \DO \\ \ind + $r \getsr I$; $R \gets r R^*$; $Y \gets r Y^*$; \\ + $h \gets H_I(R, Y)$; $c \gets r \xor h$; \\ + $\Xid{R}{map} \gets \Xid{R}{map} \cup \{ R \mapsto r \}$; \\ + $\mathbf{c}[i] \gets (R, c)$; \- \\ + \RETURN $\mathbf{c}$; + \next + Function $\id{check}_2(R', Y')$: \+ \\ + \IF $R' \notin \dom \Xid{R}{map}$ \THEN \RETURN $0$; \\ + $r \gets \Xid{R}{map}(R')$; \\ + \IF $\id{verify}(Y^*, Y'/r)$ \THEN \\ \ind + $\id{win} \gets 1$; \\ + \RETURN $1$; \- \\ + \RETURN $0$; + \end{program} + + \caption{Soundness of $\Wident$: $\id{challenges}_2$ and $\id{check}_2$} + \label{fig:wident-sound-2} + \end{figure} + + While we're generating and checking challenges in a more complicated way + here, we're not actually changing the distribution of the challenges, or + changing the winning condition. Hence $\Pr[S_2] = \Pr[S_1]$. + + Now we change the rules again. Let $\G3$ be the same as $\G2$ except that + we change the winning condition. Instead, we say that the adversary wins + if any of the queries to its random oracle $H_I(R', Y')$ would be a correct + response -- i.e., $\id{check}_2(R', Y')$ would return $1$. Since we query + the oracle on $(R', Y')$ on its behalf at the end of the game, no adversary + can do worse in this game than it does in $\G2$, so we have $\Pr[S_3] \ge + \Pr[S_2]$. (It's not hard to see that this only helps quite stupid + adversaries. We can transform any adversary into one for which equality + holds here.) + + Finally, let $\G4$ be the same as $\G3$ except that we change the way we + generate challenges again: rather than computing $h$ and setting $c \gets h + \xor r$, we just choose $c$ at random. Specifically, we use the new + function, $\id{challenges}_4$, shown in figure~\ref{fig:wident-sound-4}. + + \begin{figure} + \begin{program} + Function $\id{challenges}_4(n)$: \+ \\ + $r^* \getsr I$; $R^* \gets r^* P$; $Y^* \gets r^* X$; \\ + \FOR $i \in \Nupto{n}$ \DO \\ \ind + $r \getsr I$; $R \gets r R^*$; \\ + $c \getsr \Bin^{\ell_I}$; \\ + $\Xid{R}{map} \gets \Xid{R}{map} \cup \{ R \mapsto r \}$; \\ + $\mathbf{c}[i] \gets (R, c)$; \- \\ + \RETURN $\mathbf{c}$; + \end{program} + + \caption{Soundness of $\Wident$: $\id{challenges}_4$} + \label{fig:wident-sound-4} + \end{figure} + + Since $H_I(\cdot, \cdot)$ is a random function, the adversary can only + distinguish $\G4$ from $\G3$ if it queries its random oracle at some $(R, r + Y^*)$. But if it does this, then by the rule introduced in $\G3$ it has + already won. Therefore we must have $\Pr[S_4] = \Pr[S_3]$. + + Our $\id{challenges}_4$ function is interesting, since it doesn't actually + make use of $r^*$ or $Y^*$ when generating its challenges. This gives us + the clue we need to bound $\Pr[S_4]$: we can use adversary $A$ to solve the + multiple-guess Diffie-Hellman problem in $G$ by simulating the game $\G4$. + Specifically, we define the adversary $B$ as shown in + figure~\ref{fig:wident-sound-cdh}. That is, for each query $A$ makes to + its random oracle at a new pair $(R', Y')$, we see whether this gives us + the answer we're looking for. We have $\Pr[S_0] \le \Pr[S_4] = + \Succ{mcdh}{G}(B) \le \InSec{gdh}(G; t', q_I + q_V)$ as required. + + \begin{figure} + \begin{program} + Adversary $B^{V(\cdot)}(X, R^*)$: \+ \\ + $F \gets \emptyset$; $\Xid{R}{map} \gets \emptyset$; \\ + \FOR $i \in \Nupto{n}$ \DO \\ \ind + $r \getsr I$; $R \gets r R^*$; $c \getsr \Bin^{\ell_I}$; \\ + $\Xid{R}{map} \gets \Xid{R}{map} \cup \{ R \mapsto r \}$; \\ + $\mathbf{c}[i] \gets (R, c)$; \- \\ + $(R', Y') \gets A^{H_I(\cdot, \cdot), \id{check}(\cdot, \cdot)} + (X, \mathbf{c})$; \\ + \IF $Y' \neq \bot$ \THEN $H_I(R', Y')$; + \next + Oracle $H_I(R', Y')$: \+ \\ + \IF $(R', Y') \in \dom F$ \THEN \\ \quad + $h \gets F(x)$; \\ + \ELSE \\ \ind + $\id{check}(R', Y')$; \\ + $h \getsr \Bin^{\ell_I}$; + $F \gets F \cup \{ (R', Y') \mapsto h \}$; \- \\ + \RETURN $h$; + \- \\[\medskipamount] + Oracle $\id{check}(R', Y')$: \+ \\ + \IF $R' \in \dom \Xid{R}{map}$ \THEN + $V(Y'/\Xid{R}{map}(R'))$; + \end{program} + + \caption{Soundness of $\Wident$: reduction from MCDH} + \label{fig:wident-sound-cdh} + \end{figure} +\end{longproof} + +\subsubsection{Zero-knowledge} +Finally we must prove that $\Wident$ is (statistical) zero-knowledge -- i.e., +that, except with very small probability, Bob learns nothing of use to him +except that he's interacting with Alice. To do this, we show that, for any +algorithm $B$ which Bob might use to produce his challenge to the real Alice, +there exists a simulator $S$ which produces transcripts distributed very +similarly to transcripts of real conversations between $B$ and Alice, the +difference being that $S$ doesn't know Alice's key. We shall show that the +statistical difference between the two distributions is $2^{-\ell_I}$. + +The intuition here is that Bob ought to know what answer Alice is going to +give him when he constructs his challenge. This is certainly true if he's +honest: his challenge is $R = r P$ for some $r$ he knows, so he won't learn +anything useful when Alice responds with $x R = r X$. However, if Bob sends +a challenge $R$ when he doesn't know the corresponding $r$, he learns +something potentially useful. The accompanying check value $c = r \xor +H_I(R, r X)$ keeps him honest. + +To show this, we present an \emph{extractor} which, given any challenge $(R, +c)$ Bob can construct, and his history of random-oracle queries, either +returns a pair $(r, Y)$ such that $R = r P$ and $Y = r X$, or $\bot$; +moreover, the probability that Alice returns a response $Y' \ne \bot$ given +the challenge $(R, c)$ is $2^{-\ell}$. We can, of course, readily convert +this extractor into a simulator to prove the zero-knowledge property of our +protocol. + +We shall actually consider a slightly more complex setting. We grant Bob +access to an oracle which produces random, correctly-formed challenges. We +require this to model the legitimate challenges of other parties when we +analyse the security of our key exchange protocol. + +\begin{definition}[Discrete-log extractors] + Let $T$, $B$ be randomized algorithms. Define the game + $\Game{dl-ext}{G}(T, B)$ as shown in figure~\ref{fig:dlext}. The + \emph{success probability of $T$ as a discrete-log extractor against $B$} + is defined as + \[ \Succ{dl-ext}{G}(T, B) = \Pr[\Game{dl-ext}{G}(T, B) = 1]. \] +\end{definition} \begin{figure} \begin{program} - Procedure $\id{kx-initialize}$: \+ \\ - $\rho_A \getsr [q]$; \\ - $r_a \gets g^{\rho_A}$; \\ - $\id{state} \gets \cookie{challenge}$; \\ - $\Xid{n}{chal} \gets 0$; \\ - $k \gets \bot$; \\ - $\id{chal-commit} \gets \bot$; \\ - $\id{send}(\cookie{kx-pre-challenge}, r_A)$; \- \\[\medskipamount] - Procedure $\id{kx-receive}(\id{type}, \id{data})$: \\ \ind - \IF $\id{type} = \cookie{kx-pre-challenge}$ \THEN \\ \ind - \id{msg-pre-challenge}(\id{data}); \- \\ - \ELSE \IF $\id{type} = \cookie{kx-cookie}$ \THEN \\ \ind - \id{msg-cookie}(\id{data}); \- \\ - \ELSE \IF $\id{type} = \cookie{kx-challenge}$ \THEN \\ \ind - \id{msg-challenge}(\id{data}); \- \\ - \ELSE \IF $\id{type} = \cookie{kx-reply}$ \THEN \\ \ind - \id{msg-reply}(\id{data}); \- \\ - \ELSE \IF $\id{type} = \cookie{kx-switch}$ \THEN \\ \ind - \id{msg-switch}(\id{data}); \- \\ - \ELSE \IF $\id{type} = \cookie{kx-switch-ok}$ \THEN \\ \ind - \id{msg-switch-ok}(\id{data}); \-\- \\[\medskipamount] - Procedure $\id{msg-pre-challenge}(\id{data})$: \+ \\ - \IF $\id{state} \ne \cookie{challenge}$ \THEN \RETURN; \\ - $r \gets \id{data}$; \\ - \IF $\Xid{n}{chal} \ge \Xid{n}{chal-thresh}$ \THEN \\ \ind - $\id{send}(\cookie{kx-cookie}, r_A, \id{cookie}(r_A)))$; \- \\ - \ELSE \+ \\ - $\id{new-chal}(r)$; \\ - $\id{send}(\cookie{kx-challenge}, r_A, - \id{cookie}(r), \id{checkval}(r))$; \-\-\\[\medskipamount] - Procedure $\id{msg-cookie}(\id{data})$: \+ \\ - \IF $\id{state} \ne \cookie{challenge}$ \THEN \RETURN; \\ - $(r, c_A) \gets \id{data}$; \\ - \IF $c_A \ne \id{cookie}(r_A)$ \THEN \RETURN; \\ - $\id{new-chal}(r)$; \\ - $\id{send}(\cookie{kx-challenge}, r_A, - \id{cookie}(r), \id{checkval}(r))$; \- \\[\medskipamount] - Procedure $\id{msg-challenge}(\id{data})$: \+ \\ - \IF $\id{state} \ne \cookie{challenge}$ \THEN \RETURN; \\ - $(r, c_A, v) \gets \id{data}$; \\ - \IF $c_A \ne \id{cookie}(r_A)$ \THEN \RETURN; \\ - $i \gets \id{check-reply}(\bot, r, v)$; \\ - \IF $i = \bot$ \THEN \RETURN; \\ - $k \gets \id{chal-tab}[i].k$; \\ - $y \gets \id{encrypt}(k, \cookie{kx-reply}, r^\alpha)$; \\ - $\id{send}(\cookie{kx-reply}, c_A, \id{cookie}(r), - \id{checkval}(r), y)$ + $\Game{dl-ext}{G}(T, B):$ \+ \\ + $H_I \getsr \Func{G^2}{\Bin^{\ell_I}}$; + $Q_H \gets \emptyset$; $Q_C \gets \emptyset$; \\ + $(x, X) \gets \id{setup}()$; \\ + $(R, c) \gets B^{\Xid{H_I}{trap}(\cdot, \cdot), C()}(x, X)$; \\ + $(r, Y) \gets T(R, c, Q_H)$; \\ + $Y' \gets x R$; $h' \gets H_I(R, Y')$; $r' \gets c \xor h'$; \\ + \IF $r \ne \bot$ \THEN \\ \quad + \IF $Y = \bot \lor R \ne r P \lor Y \ne Y'$ \THEN \RETURN $0$; \\ + \IF $R = r' P$ \THEN $(r^*, Y^*) \gets (r', Y')$; \\ + \ELSE $(r^*, Y^*) \gets (\bot, \bot)$; \\ + \IF $(R, c) \in Q_C$ \THEN \RETURN $1$; \\ + \IF $(r, Y) = (r', Y')$ \THEN \RETURN $1$; \\ + \RETURN $0$; \next - Procedure $\id{msg-reply}(\id{data})$: \+ \\ - $(c, c_A, v, y) \gets \id{data}$; \\ - \IF $c_A \ne \id{cookie}(r_A)$ \THEN \RETURN; \\ - $i \gets \id{find-chal}(c)$; \\ - \IF $i = \bot$ \THEN \RETURN; \\ - \IF $\id{check-reply}(i, \id{chal-tab}[i].r, v) = \bot$ \THEN \\ \ind - \RETURN; \- \\ - $k \gets \id{chal-tab}[i].k$; \\ - $x \gets \id{decrypt}(k, \cookie{kx-reply}, y)$; \\ - \IF $x = \bot$ \THEN \RETURN; \\ - \IF $x \ne b^{\rho_A}$ \THEN \RETURN; \\ - $\id{state} \gets \cookie{commit}$; \\ - $\id{chal-commit} \gets \id{chal-tab}[i]$; \\ - $w \gets H(\cookie{switch-request}, c_A, c)$; \\ - $x \gets \id{chal-tab}[i].r^\alpha$; \\ - $y \gets \id{encrypt}(k, (x, \cookie{kx-switch}, w))$; \\ - $\id{send}(\cookie{kx-switch}, c_A, c, y)$; \-\\[\medskipamount] - Procedure $\id{msg-switch}(\id{data})$: \+ \\ - $(c, c_A, y) \gets \id{data}$; \\ - \IF $c_A \ne \cookie(r_A)$ \THEN \RETURN; \\ - $i \gets \id{find-chal}(c)$; \\ - \IF $i = \bot$ \THEN \RETURN; \\ - $k \gets \id{chal-tab}[i].k$; \\ - $x \gets \id{decrypt}(k, \cookie{kx-switch}, y)$; \\ - \IF $x = \bot$ \THEN \RETURN; \\ - $(x, w) \gets x$; \\ - \IF $\id{state} = \cookie{challenge}$ \THEN \\ \ind - \IF $x \ne b^{\rho_A}$ \THEN \RETURN; \\ - $\id{chal-commit} \gets \id{chal-tab}[i]$; \- \\ - \ELSE \IF $c \ne \id{chal-commit}.c$ \THEN \RETURN; \\ - \IF $w \ne H(\cookie{switch-request}, c, c_A)$ \THEN \RETURN; \\ - $w \gets H(\cookie{switch-confirm}, c_A, c)$; \\ - $y \gets \id{encrypt}(y, \cookie{kx-switch-ok}, w)$; \\ - $\id{send}(\cookie{switch-ok}, y)$; \\ - $\id{done}(k)$; \- \\[\medskipamount] - Procedure $\id{msg-switch-ok}(\id{data})$ \+ \\ - \IF $\id{state} \ne \cookie{commit}$ \THEN \RETURN; \\ - $y \gets \id{data}$; \\ - $k \gets \id{chal-commit}.k$; \\ - $w \gets \id{decrypt}(k, \cookie{kx-switch-ok}, y)$; \\ - \IF $w = \bot$ \THEN \RETURN; \\ - $c \gets \id{chal-commit}.c$; \\ - $c_A \gets \id{cookie}(r_A)$; \\ - \IF $w \ne H(\cookie{switch-confirm}, c, c_A)$ \THEN \RETURN; \\ - $\id{done}(k)$; + Oracle $\Xid{H_I}{trap}(R', Y')$: \+ \\ + $h \gets H_I(R', Y')$; \\ + $Q_H \gets Q_H \cup \{(R', Y', h)\}$; \\ + \RETURN $h$; \- \\[\medskipamount] + Oracle $C()$: \+ \\ + $r \getsr \gf{q}$; \\ + $R \gets r P$; $c \gets r \xor H_I(R, r X)$; \\ + $Q_C \gets Q_C \cup \{(R, c)\}$; \\ + \RETURN $(R, c)$ \end{program} - \caption{The key-exchange protocol: message handling} - \label{fig:kx-messages} + \caption{Discrete log extraction game: $\Game{dl-ext}{G}(T, B)$} + \label{fig:dlext} \end{figure} +Let's unpack this definition slightly. We make the following demands of our +extractor. +\begin{itemize} +\item It is given a bare `transcript' of $B$'s execution. In particular, it + is given only its output and a list of $B$'s random-oracle queries in no + particular order. +\item While the extractor is not given the private key~$x$, the adversary~$B$ + is given the private key. +\item We require that, if the extractor produces values $r, Y \ne \bot$ then + $r$ and $Y$ are \emph{correct}; i.e., that $R = r P$ and $Y = x R$. +\item The extractor is explicitly \emph{not} given the outputs of the + challenge-generation oracle $C()$, nor of the random-oracle queries issued + by $C()$. However, we allow the extractor to fail (i.e., return $\bot$) if + $B$ simply parrots one of its $C$-outputs. +\item The extractor is allowed -- indeed \emph{required} -- to fail if the + challenge $(R, c)$ is \emph{invalid} (i.e., Alice would return $\bot$ given + the challenge). +\end{itemize} +The resulting definition bears a striking similarity to the concept of +\emph{plaintext awareness} in \cite{Bellare:1998:RAN}. + +Such an extractor indeed exists, as the following lemma states. +\begin{lemma}[Effectiveness of extractor $T_\Wident$] + \label{lem:dlext} + There exists a \emph{universal discrete-log extractor} $T_\Wident$, shown + in figure~\ref{fig:twident}, such that, for any algorithm $B$, + \[ \Succ{dl-ext}{G}(T_\Wident, B) \ge 1 - \frac{1}{2^{\ell_I}}. \] + Moreover, if $B$ issues at most $q_H$ random-oracle queries, then the + running time of $T_\Wident$ is $O(q_H)$. +\end{lemma} +\ifshort +The proof of this lemma is given in the full version of this paper. +\else +We prove this result at the end of the section. For now, let us see how to +prove that $\Wident$ is zero-knowledge. +\fi + \begin{figure} \begin{program} - Structure $\id{chal-slot}$: \+ \\ - $r$; $c$; $\id{replied}$; $k$; \- \\[\medskipamount] - Function $\id{find-chal}(c)$: \+ \\ - \FOR $i = 0$ \TO $\Xid{n}{chal}$ \DO \\ \ind - \IF $\id{chal-tab}[i].c = c$ \THEN \RETURN $i$; \- \\ - \RETURN $\bot$; \- \\[\medskipamount] - Function $\id{cookie}(r)$: \+ \\ - \RETURN $H(\cookie{cookie}, r)$; \- \\[\medskipamount] - Function $\id{check-reply}(i, r, v)$: \+ \\ - \IF $i \ne \bot \land \id{chal-tab}[i].\id{replied} = 1$ \THEN \\ \ind - \RETURN $i$; \- \\ - $\rho \gets v \xor H(\cookie{expected-reply}, r, r_A, r^\alpha)$; \\ - \IF $g^\rho \ne r$ \THEN \RETURN $\bot$; \\ - \IF $i = \bot$ \THEN $i \gets \id{new-chal}(r)$; \\ - $\id{chal-tab}[i].k \gets \id{gen-keys}(r_A, r, r^{\rho_A})$; \\ - $\id{chal-tab}[i].\id{replied} \gets 1$; \\ - \RETURN $i$; - \next - Function $\id{checkval}(r)$: \\ \ind - \RETURN $\rho_A \xor H(\cookie{expected-reply}, - r_A,r, b^{\rho_A})$; \- \\[\medskipamount] - Function $\id{new-chal}(r)$: \+ \\ - $c \gets \id{cookie}(r)$; \\ - $i \gets \id{find-chal}(c)$; \\ - \IF $i \ne \bot$ \THEN \RETURN $i$; \\ - \IF $\Xid{n}{chal} < \Xid{n}{chal-max}$ \THEN \\ \ind - $i \gets \Xid{n}{chal}$; \\ - $\id{chal-tab}[i] \gets \NEW \id{chal-slot}$; \\ - $\Xid{n}{chal} \gets \Xid{n}{chal} + 1$; \- \\ + Extractor $T_\Wident(R, c, Q_H)$: \+ \\ + \FOR $(R', Y', h)$ \IN $Q_H$ \DO \\ \ind + $r \gets h \xor c$; \\ + \IF $R = R' = r P \land Y' = r X$ \THEN \RETURN $(r, Y')$; \- \\ + \RETURN $(\bot, \bot)$; + \end{program} + + \caption{The discrete-log extractor $T_\Wident$} + \label{fig:twident} +\end{figure} + +We use the set-up described in section~\ref{sec:sim}. Our initialization +function~$I_\Wident$ just chooses a random $x \in \gf{q}$ as the world +private input and sets $X = x P$ as the common input. In the `real world', +the adversary is allowed to submit a (single) challenge to the prover; it is +given the prover's response, and must then compute its output. This is shown +on the left hand side of figure~\ref{fig:wident-sim}. + +The zero-knowledge property of the scheme is described by the following +theorem. +\begin{theorem}[Statistical zero-knowledge of $\Wident$] + \label{thm:wident-zk} + Let $I_\Wident$, $W_\Wident$ and $S_\Wident$ be the real-prover world and + simulator shown in figure~\ref{fig:wident-sim}. Then, for any~$t$, + $q_I$ and $q_C$, + \[ \InSec{sim}(W_\Wident, I_\Wident, S_\Wident; t, q_I, q_C, 0) \le + \frac{q_C}{2^\ell_I}. + \] + where $q_C$ is the maximum number of challenges allowed by the adversary. +\end{theorem} +\begin{longproof}{} + The simulator simply uses the extractor~$T_\Wident$ to extract the answer + from the adversary's history of random oracle queries. Observe that + $S_\Wident$ is a fake-world simulator. By lemma~\ref{lem:dlext}, the + extractor fails with probability only $2^{-\ell_I}$. The theorem follows + by a simple union bound and proposition~\ref{prop:fakesim}. +\end{longproof} + +%\ifshort\else +\begin{figure} + \begin{program} + Initialization function $I_\Wident()$: \+ \\ + $x \getsr \gf{q}$; \\ + $X \gets x P$; \\ + \RETURN $(x, X)$; + \- \\[\medskipamount] + Real-prover world $W_\Wident^{H_I(\cdot, \cdot)} + ((x, X), \sigma, \tau, \mu)$: \+ \\ + \IF $\tau = \cookie{challenge}$ \THEN \\ \ind + $(R, c) \gets \mu$; \\ + $Y \gets \id{response}^{H_I(\cdot, \cdot)}(R, c, x)$; \\ + \RETURN $(1, Y)$; \- \\ + \ELSE \\ \ind + \RETURN $(\sigma, \bot)$; + \next + Simulator $S_\Wident$'s fake world \\ + \hspace{1in} $W_{\text{sim}}^{H_I(\cdot, \cdot)} + ((X, u), \sigma, \tau, \mu)$: \+ \\ + \IF $\tau = \cookie{init}$ \THEN \\ \ind + \RETURN $(\emptyset, \emptystring)$; \- \\ + $Q_H \gets \sigma$; \\ + \IF $\tau = \cookie{challenge}$ \THEN \\ \ind + $(R, c) \gets \mu$; \\ + $(r, Y) \gets T_\Wident(R, c, Q_H)$; \\ + \RETURN $(Q_H, Y)$; \- \\ + \ELSE \IF $\tau = \cookie{random}$ \THEN \\ \ind + $(i, (R', Y'), h) \gets \mu$; \\ + $Q_H \gets Q_H \cup \{(R', Y', h)\}$; \\ + \RETURN $(Q_H, \emptystring)$; \- \\ \ELSE \\ \ind - $i \getsr [\Xid{n}{chal-max}]$; \- \\ - $\id{chal-tab}[i].r \gets r$; \\ - $\id{chal-tab}[i].c \gets c$; \\ - $\id{chal-tab}[i].\id{replied} \gets 0$; \\ - $\id{chal-tab}[i].k \gets \bot$; \\ - \RETURN $i$; + \RETURN $(\sigma, \bot)$; \end{program} - \caption{The key-exchange protocol: support functions} - \label{fig:kx-support} + \caption{Real-prover and simulator for zero-knowledge of $\Wident$} + \label{fig:wident-sim} \end{figure} +%\fi + +\ifshort\else +We now return to proving that the extractor $T_\Wident$ functions as claimed. +The following two trivial lemmata will be useful, both now and later. +\begin{lemma}[Uniqueness of discrete-logs] + \label{lem:unique-dl} + Let $G = \langle P \rangle$ be a cyclic group. For any $X \in G$ there is + a unique $x \in \gf{q}$ where $X = x P$. +\end{lemma} +\begin{proof} + Certainly such an $x$ exists, since $G$ is cyclic and finite. Suppose $X = + x P = x' P$: then $0 = x P - x' P = (x - x') P$. Hence $(x - x')$ is a + multiple of $q$, i.e., $x = x'$. +\end{proof} +\begin{lemma}[Uniqueness of check values] + \label{lem:unique-c} + Let $G = \langle P \rangle$ be a cyclic group of prime order $q$; let $H_I$ + be a function $H_I\colon \Bin^{2\ell_G} \to \Bin^{\ell_I}$. Fix some $x + \in \gf{q}$ and define the set + \[ V_x = \bigl\{\, (R, c) \in G \times \Bin^{\ell_I} \bigm| + R = \bigl( c \xor H_I(R, x R) \bigr) P \,\bigr\}. + \] + Then, for any $R$, $c$, $c'$, if $(R, c) \in V_x$ and $(R, c') \in V_x$ + then $c = c'$. +\end{lemma} +\begin{proof} + From lemma~\ref{lem:unique-dl}, we see that there is a unique $r \in \gf{q}$ + for which $R = r P$. Now, if $(R, c) \in V_x$, we must have $r = c \xor + H_I(R, x R)$. It follows that $c = r \xor H_I(R, x R)$. +\end{proof} -%%%-------------------------------------------------------------------------- +\begin{proof}[Proof of lemma~\ref{lem:dlext}] + Let $B$ be any randomized algorithm, and let $(R, c, Q_H)$ be as given to + the extractor by $\Game{dl-ext}{G}(T_\Wident, B)$. Let the quantities + $H_I$, $Q_C$, $r$, $r'$, $x$ and $X$ be as in that game. + + Suppose that the extractor returns values $(r, Y) \ne (\bot, \bot)$. Let + $h = r \xor c$; then there must be a query $(R, Y, h) \in Q_H$, and we have + $R = r P$ and $Y = r X = r (x P) = x (r P) = x R = Y'$, so the extractor's + output must be correct unless it fails. + + Furthermore, in the case where the extractor did not fail, we have $h = + H_I(R, Y) = H_I(R, Y')$ and $c = r \xor h$, so the challenge was valid. + Therefore, if the challenge was invalid, the extractor will fail. + + We now deal with the challenge-generation oracle. Suppose that $(R, c') + \in Q_C$ for some $c'$. Now, if $c = c'$ then $(R, c')$ is a repeat of + some challenge from the challenge-generation oracle, and the extractor is + permitted to fail. On the other hand, suppose $c \ne c'$; then, the + challenge $(R, c)$ must be invalid by lemma~\ref{lem:unique-c}, so the + extractor is required to fail, and we have established that indeed it will. + From now on, suppose that $R$ is distinct from all the $R$-values returned + by $C()$. + + Let $Y = x R$. Suppose that $B$ queried its random oracle at $(R, Y)$. + Let $h = H_I(Y)$, so $r' = c \xor h$. If the challenge is valid then $R = + r' P$; therefore $Y = x R = x r' P = r' X$, so we have $(R, Y, h) \in Q_H$ + with $R = r P$ and $Y = r X$. Hence the extractor returns $r = r'$ as + required. + + It remains to deal with the case where there is no random-oracle query at + $(R, Y)$. But then $h = H_I(R, Y)$ is uniformly distributed, and + independent of the entire game up to this point. Let $r$ be the correct + discrete log of $R$; by lemma~\ref{lem:unique-dl} there is only one + possible value. The extractor always fails under these circumstances, but + a correct responder would reply with probability + \[ \Pr[h = c \xor r] = \frac{1}{2^{\ell_I}}. \] + This concludes the proof. +\end{proof} +\begin{remark} + Note that the fact that the algorithm~$B$ was given the private key is + irrelevant to the above argument. However, we shall need this property + when we come to prove deniability for the key-exchange protocol. +\end{remark} +\begin{remark} + It's easy to see from the above proof that the extractor works flawlessly + on the `honest verifier' algorithm $\id{challenge}$ shown in + figure~\ref{fig:wident-ro}. This shows that $\Wident$ is perfect + zero-knowledge against honest verifiers. We're much more interested in + dishonest verifiers, though. +\end{remark} +\fi -\section{CBC mode encryption} -\label{sec:cbc} -Our implementation of the Wrestlers Protocol uses Blowfish -\cite{Schneier:1994:BEA} in CBC mode. However, rather than pad plaintext -messages to a block boundary, with the ciphertext expansion that entails, we -use a technique called \emph{ciphertext stealing} -\cite[section 9.3]{Schneier:1996:ACP}. +\ifshort\else +\subsection{An identity-based identification scheme} +\label{sec:wident-id} + +Boneh and Franklin \cite{Boneh:2003:IBE} showed how to construct an +identity-based encryption scheme using bilinear pairings. The resulting +encryption scheme looks somewhat like a pairing-based version of ElGamal's +encryption scheme \cite{ElGamal:1985:PKCb}. We can easily apply their +techniques to our identification protocol, and thereby obtain an +identity-based identification scheme. Providing the necessary formalisms to +prove theorems analogous to our theorems~\ref{thm:wident-sound} +and~\ref{thm:wident-zk} would take us too far from our objectives; but given +appropriate security notions, we can readily adapt our existing proofs to the +new setting. + +\subsubsection{Bilinear pairings} +Before we describe the necessary modifications to the protocol, we first give +a (very brief!) summary of cryptographic pairings. (The Boneh-Franklin paper +\cite{Boneh:2003:IBE} gives more detail; also \cite{Menezes:2005:IPB} +provides a useful introduction to the topic.) + +Let $(G, +)$, $(G', +)$ and $(G_T, \times)$ be cyclic groups with prime order +$q$; let $P \in G$ and $P' \in G'$ be elements of order $q$ in $G$ and $G'$ +respectively. We say that a mapping $\hat{e}\colon G \times G' \to G_T$ is a +\emph{non-degenerate bilinear pairing} if it satisfies the following +properties. +\begin{description} +\item[Bilinearity] For all $R \in G$ and $S', T' \in G'$, we have $\hat{e}(R, + S' + T') = \hat{e}(R, S')\,\hat{e}(R, T')$; and for all $R, S \in G$ and $T' + \in G'$ we have $\hat{e}(R + S, T') = \hat{e}(R, T')\,\hat{e}(S, T')$. +\item[Non-degeneracy] $\hat{e}(P, P') \ne 1$. +\end{description} +For practical use, we also want $\hat{e}(\cdot, \cdot)$ to be efficient to +compute. The reader can verify that $\hat{e}(a P, b P') = \hat{e}(P, +P')^{ab}$. It is permitted for the two groups $G$ and $G'$ to be equal. + +We require a different intractability assumption, specifically that the +\emph{bilinear} Diffie-Hellman problem (BDH) -- given $(a P, b P, a P', c P') +\in G^2 \times G'^2$, find $\hat{e}(P, P')^{abc} \in G_T$ -- is difficult. +This implies the difficulty of the computational Diffie-Hellman problem in +all three of $G$, $G'$ and~$G_T$. + +\subsubsection{The identity-based scheme} +We need a trusted authority; following \cite{Schneier:1996:ACP} we shall call +him Trent. Trent's private key is $t \in \gf{q}$; his public key is $T = +t P$. + +Finally, we need cryptographic hash functions $H_I\colon G \times G_T \to +\Bin^{\ell_I}$ and $\Hid\colon \Bin^* \to G'$; a formal security analysis +would model these as random oracles. + +Alice's public key is $A = \Hid(\texttt{Alice}) \in G'$. Her private key is +$K_A = t A \in G'$ -- she needs Trent to give this to her. Bob can interact +with Alice in order to verify her identity as follows. +\begin{enumerate} +\item Bob computes $\gamma_A = \hat{e}(T, A) \in G_T$. (He can do this once + and store the result if he wants, but it's not that onerous to work it out + each time.) +\item Bob chooses $r \inr \gf{q}$, and sets $R = r P$. He also computes + $\psi = \gamma_A^r$, $h = H_I(R, \psi)$ and $c = r \xor h$. He sends his + challenge $(R, c)$ to Alice. +\item Alice receives $(R', c')$. She computes $\psi' = \hat{e}(R, K_A)$, $h' + = H_I(R', \psi')$, and $r' = c' \xor h')$. She checks that $R' = r' P$; if + so, she sends $\psi'$ back to Bob; otherwise she refuses to talk to him. +\item Bob receives $\psi'$. If $\psi = \psi'$ then he accepts that he's + talking to Alice. +\end{enumerate} +This works because $\psi = \gamma_A^r = \hat{e}(T, A)^r = \hat{e}(t P, A)^r = +\hat{e}(r P, A)^t = \hat{e}(R, t A) = \psi'$. + +\subsubsection{Informal analysis} +An analogue to lemma~\ref{lem:dlext} can be proven to show how to extract $r$ +from a verifier's random-oracle queries; statistical zero knowledge would +then follow easily, as in theorem~\ref{thm:wident-zk}. Soundness is +intuitively clear, since an adversary must compute $\psi = \hat{e}(P, +P')^{art}$ given $A = a P'$, $R = r P$ and $T = t P$, which is an instance of +the BDH problem. An analogue of theorem~\ref{thm:wident-sound} would have to +prove this for an adversary capable of making identity requests as well as +obtaining challenges. Finally, our key-exchange protocol can be constructed +out of this identity-based identification scheme, yielding an identity-based +authenticated key-exchange protocol. We leave it to the reader to work +through the details. +\fi -\subsection{Standard CBC mode} -Suppose $E$ is an $\ell$-bit pseudorandom permutation. Normal CBC mode works -as follows. Given a message $X$, we divide it into blocks $x_0, x_1, \ldots, -x_{n-1}$. Choose a random \emph{initialization vector} $I \inr \Bin^\ell$. -Before passing each $x_i$ through $E$, we XOR it with the previous -ciphertext, with $I$ standing in for the first block: -\begin{equation} - y_0 = E_K(x_0 \xor I) \qquad - y_i = E_K(x_i \xor y_{i-1} \ \text{(for $1 \le i < n$)}. -\end{equation} -The ciphertext is then the concatenation of $I$ and the $y_i$. Decryption is -simple: -\begin{equation} - x_0 = E^{-1}_K(y_0) \xor I \qquad - x_i = E^{-1}_K(y_i) \xor y_{i-1} \ \text{(for $1 \le i < n$)} -\end{equation} -See figure~\ref{fig:cbc} for a diagram of CBC encryption. +\ifshort\else +\subsection{Comparison with the protocol of Stinson and Wu} +\label{sec:stinson-ident} + +Our protocol is similar to a recent proposal by Stinson and Wu +\cite{cryptoeprint:2006:337}. They restrict their attention to Schnorr +groups $G \subset \F_p^*$. Let $\gamma$ be an element of order $q = \#G$. +The prover's private key is $a \inr \gf{q}$ and her public key is +$\alpha = \gamma^a$. In their protocol, the challenger chooses +$r \inr \gf{q}$, computes $\rho = \gamma^r$ and $\psi = \alpha^r$, and sends +a challenge $(\rho, H(\psi))$. The prover checks that $\rho^q \ne 1$, +computes $\psi = \rho^a$, checks the hash, and sends $\psi$ back by way of +response. They prove their protocol's security in the random-oracle model. + +Both the Wrestlers protocol and Stinson-Wu require both prover and verifier +to compute two exponentiations (or scalar multiplications) each. The +sizes of the messages used by the two protocols are also identical. + +(An earlier version of the Stinson-Wu protocol used a cofactor +exponentiation: if we set $f = (p - 1)/q$, then we use $\psi = \alpha^{rf}) = +\rho^{af} = \gamma^{afr}$. This is more efficient in typical elliptic curve +subgroups, since the cofactor of such subgroups is usually small: indeed, +\cite{SEC1} recommends rejecting groups with cofactor $f > 4$. However, in +the Schnorr groups used by Stinson and Wu, the cofactor is much larger than +$q$, and their new variant is more efficient.) + +We note that the zero-knowledge property of the Stinson-Wu protocol requires +the Diffie-Hellman knowledge of exponent assumption (KEA). Very briefly: +suppose $A$ is a randomized algorithm which takes as input $X \in G$ and +outputs a pair $(r P, r X)$; intuitively, the KEA asserts $A$ must have done +this by choosing $r$ somehow and then computing its output from it. +Formally, it asserts the existence of an `extractor' algorithm which takes as +input the element $X$ and the random coins used by $A$ and outputs $r$ with +high probability. This is a very strong assumption, and one which is +unnecessary for our protocol, since we can present an \emph{explicit} +extractor. + +The KEA assumption as stated in \cite{cryptoeprint:2006:337} allows the +extractor to fail with some negligible probability, over and above the +probability that a dishonest verifier managed to guess the correct +$h = H(\psi)$ without making this random-oracle query. Not only does our +protocol achieve zero- knowledge without the KEA, our extractor is, in this +sense, `perfect'. + +Our protocol is just as strong as Stinson-Wu under attack from active +intruders: see table~\ref{tab:wident-active} for a very brief sketch of the +case-analysis which would be the basis of a proof of this. + +\begin{table} + \begin{tabular}[C]{|*{3}{c|}p{8cm}|} + \hlx{hv[1]} + \multicolumn{2}{|c|}{\textbf{Challenge}} & + \textbf{Response} & + \textbf{Security} + \\ \hlx{v[1]hv} + %% unpleasant hacking to make the R and c columns the same width :-( + \settowidth{\dimen0}{\textbf{Challenge}}% + \dimen0=.5\dimen0 + \advance\dimen0by-\tabcolsep + \advance\dimen0by-.5\arrayrulewidth + \hbox to\dimen0{\hfil$R$\hfil} + & $c$ & $Y$ & Nothing to prove. \\ \hlx{v} + $R$ & $c'$ & --- & Prover rejects by lemma~\ref{lem:unique-c}; + $Y'$ probably wrong by + theorem~\ref{thm:wident-sound}. \\ \hlx{v} + $R$ & $c$ & $Y'$ & Response is incorrect. \\ \hlx{v} + $R'$ & --- & $Y$ & Response is incorrect. \\ \hlx{v} + $R'$ & $c$ & $Y'$ & Prover rejects with probability $1 - 2^{-\ell_I}$; + $Y'$ probably wrong by + theorem~\ref{thm:wident-sound}. \\ \hlx{v} + $R'$ & $c'$ & $Y'$ & Simulate prover using extractor + (lemma~\ref{lem:dlext}); $Y'$ probably wrong by + theorem~\ref{thm:wident-sound}. \\ \hlx{vh} + \end{tabular} + + \caption{Security of $\Wident$ against active intruders (summary)} + \label{tab:wident-active} +\end{table} + +An identity-based analogue of Stinson-Wu can be defined using a bilinear +pairing, just as we did in section~\ref{sec:wident-id}. However, to prove +the zero-knowledge property, one needs to make a bilinear analogue of the +knowledge of exponent assumption. + +We suspect that a key-exchange protocol like ours can be constructed using +Stinson-Wu rather than the Wrestlers identification scheme. We haven't, +however, gone through all the details, since we believe our protocol is just +as efficient and is based on much more conservative assumptions. +\fi + +%%%-------------------------------------------------------------------------- + +\section{A simple key-exchange protocol} +\label{sec:kx} + +In this section, we describe a simple key-exchange protocol built out of the +identification protocol shown previously. + +The key-exchange protocol arises from the following observation. If Bob +sends a challenge, presumably to Alice, and gets a correct response, then not +only did he really send the challenge to Alice but he knows that she received +it correctly. + +So, if Alice and Bob authenticate each other, by the end of it, they should +each have chosen a random private value, sent the corresponding public value +to the other, and been convinced that it arrived safely. + +Unfortunately, life isn't quite this kind, and we have to do some more work +to make this scheme secure. + + +Our key exchange protocol essentially consists of two parallel instances of +the identification protocol. If Alice receives a correct response to her +challenge, she will know that Bob received her challenge correctly, and +\emph{vice versa}. If we let Alice's challenge be $R_0 = r_0 P$ and Bob's +challenge be $R_1 = r_1 P$ then each can compute a shared secret $Z = r_0 R_1 += r_0 r_1 P = r_1 R_0$ unknown to an adversary. There are, unfortunately, a +few subtleties involved in turning this intuition into a secure key-exchange +protocol, which we now describe. + + +\subsection{Overview} +\label{sec:kx-overview} + +We present a quick, informal description of our basic key-exchange protocol. +In addition to our group $G$, we shall also need a secure symmetric +encryption scheme $\E = (\kappa, E, D)$, and two secure hash functions +$H_I\colon \Bin^{2\ell_G} \to \Bin^{\ell_I}$ and $H_K\colon \Bin^{\ell_G+1} +\to \Bin^\kappa$. + +Suppose that Alice's and Bob's private keys are $a$ and $b$ respectively, and +their public keys are $A = a P$ and $B = b P$. +\begin{enumerate} +\item Alice chooses a random index $r \inr \gf{q}$. She computes $R = r P$ and + $c = r \xor H_I(R, r B)$. She sends the pair $(R, c)$ to Bob. +\item Similarly, Bob chooses a random $s \inr \gf{q}$. He computes $S = s P$ + and $d = s \xor H_I(S, s A)$. He sends $(S, d)$ to Alice. +\item Alice receives $(S', d')$ from Bob. She computes $s' = d' \xor H_I(S', + a S')$, and verifies that $S' = s' P$. If so, she computes $K_A = H_K(0 + \cat r S')$, and sends $R, E_{K_A}(a S')$ to Bob. +\item Similarly, Bob receives $(R', c')$ from Alice. He verifies that $R' = + \bigl( c' \xor H_I(R', b R') \bigr) P$. If so, he computes $K_B = H_K(0 + \cat s R')$ and sends S, $E_{K_B}(b R')$ to Alice. +\item Alice receives a ciphertext $(S'', \chi_B)$ from Bob. She checks that + $S'' = S'$, decrypts $\chi_B$, and checks that $D_{K_A}(\chi_B) = r B$. If + so, she uses $H_K(1 \cat r S')$ as her shared secret. +\item Similarly, Bob receives $(R'', \chi_A)$ from Alice, and checks $R'' = + R'$ and $D_{K_B}(\chi_A) = s A$. If so, he uses $H_K(1 \cat s R')$ as his + shared secret. +\end{enumerate} +This is the Wrestlers Key Exchange protocol, $\Wkx^{G, \E}$ (again, we omit +the superscripts when referring to the general protocol, or when confusion is +unlikely). A diagrammatic summary of the protocol is shown in +figure~\ref{fig:wkx}. \begin{figure} - \[ \begin{graph} - []!{0; <0.85cm, 0cm>: <0cm, 0.5cm>::} - *+=(1, 0)+[F]{\mathstrut x_0}="x" - :[dd] *{\xor}="xor" - [ll] *+=(1, 0)+[F]{I} :"xor" - :[dd] *+[F]{E}="e" :[ddd] *+=(1, 0)+[F]{\mathstrut y_0}="i" - "e" [l] {K} :"e" - [rrruuuu] *+=(1, 0)+[F]{\mathstrut x_1}="x" - :[dd] *{\xor}="xor" - "e" [d] :`r [ru] `u "xor" "xor" - :[dd] *+[F]{E}="e" :[ddd] - *+=(1, 0)+[F]{\mathstrut y_1}="i" - "e" [l] {K} :"e" - [rrruuuu] *+=(1, 0)+[F--]{\mathstrut x_i}="x" - :@{-->}[dd] *{\xor}="xor" - "e" [d] :@{-->}`r [ru] `u "xor" "xor" - :@{-->}[dd] *+[F]{E}="e" :@{-->}[ddd] - *+=(1, 0)+[F--]{\mathstrut y_i}="i" - "e" [l] {K} :@{-->}"e" - [rrruuuu] *+=(1, 0)+[F]{\mathstrut x_{n-1}}="x" - :[dd] *{\xor}="xor" - "e" [d] :@{-->}`r [ru] `u "xor" "xor" - :[dd] *+[F]{E}="e" :[ddd] - *+=(1, 0)+[F]{\mathstrut y_{n-1}}="i" - "e" [l] {K} :"e" - \end{graph} \] - - \caption{Encryption using CBC mode} - \label{fig:cbc} + \begin{description} + \item[Setup] Group $G = \langle P \rangle$; $\#G = q$ is prime. + $H_I(\cdot, \cdot)$ and $H_K(\cdot)$ are secure hashes. $\E = (\kappa, + E, D)$ is an IND-CCA2 symmetric encryption scheme. + \item[Parties] $U_i$ for $0 \le i < n$. + \item[Private keys] $x_i \inr \gf{q}$. + \item[Public keys] $X_i = x_i P$. + \end{description} + \begin{protocol} + $r_i \getsr I$; $R_i \gets r_i P$; & + $r_j \getsr I$; $R_j \gets r_j P$; \\ + $c_i \gets r_i \xor H_I(R_i, r_i X_j)$; & + $c_j \gets r_j \xor H_I(R_j, r_j X_i)$; \\ + \send{->}{(R_i, c_i)} + \send{<-}{(R_j, c_j)} + Check $R_j = \bigl(c_j \xor H_I(x_i R_j)\bigr) P$; & + Check $R_i = \bigl(c_i \xor H_I(x_j R_i)\bigr) P$; \\ + $Z \gets r_i R_j$; $(K_0, K_1) \gets H_K(Z)$; & + $Z \gets r_j R_i$; $(K_0, K_1) \gets H_K(Z)$; \\ + $\chi_i \gets E_{K_0}(x_i R_j)$; & + $\chi_j \gets E_{K_0}(x_j R_i)$; \\ + \send{->}{(R_i, \chi_i)} + \send{<-}{(R_j, \chi_j)} + Check $D_{K_0}(\chi_j) = r_i X_j$; & + Check $D_{K_0}(\chi_i) = r_j X_i$; \\ + Shared key is $K_1$. & Shared key is $K_1$. + \end{protocol} + + \caption{Summary of the Wrestlers Key Exchange protocol, $\Wkx$} + \label{fig:wkx} \end{figure} -\begin{definition}[CBC mode] - \label{def:cbc} - Let $P\colon \keys P \times \Bin^\ell to \Bin^\ell$ be a pseudorandom - permutation. We define the symmetric encryption scheme - $\Xid{\mathcal{E}}{CBC}^P = (\Xid{E}{CBC}^P, \Xid{D}{CBC}^P)$ for messages - in $\Bin^{\ell\Z}$ by setting $\keys \Xid{\mathcal{E}}{CBC} = \keys P$ and - defining the encryption and decryption algorithms as follows: +Assume, for the moment, that Alice and Bob's messages are relayed honestly. +Then: +\begin{itemize} +\item $a S' = a S = a (s P) = s (a P) = s A$, so $s' = d' \xor H_I(S' a S') = + d \xor H_I(S, s A) = s$, and $S' = S = s P = s' P$, and therefore Alice + responds to Bob's message; +\item similarly $b R' = r B$, so $r' = r$ and $R' = r' P$, and therefore Bob + responds to Alice's message; +\item $b R' = b R = b (r P) = r (b P) = r B$, and $a S' = a S = a (s P) = s + (a P) = s A$, and therefore both parties compute their responses correctly; + and +\item $r S' = r S = r (s P) = s (r P) = s R = s R'$, so $K_A = K_B$, and + therefore they can decrypt each others' responses, and agree the same + shared secret. +\end{itemize} +This shows that the protocol is basically valid, but says little about its +security. The remainder of this section will describe our protocol in more +formal detail, and prove its security in a model with multiple parties and an +adversary who controls the network. + +Observe that the protocol as we've presented here is \emph{symmetrical}. +There's no notion of `initiator' or `responder'. There are a total of four +messages which must be sent before both parties accept. However, this can be +reduced to three by breaking the symmetry of the protocol and combining one +or other party's challenge and response messages. We choose to analyse the +symmetrical version, since to do so, it suffices to consider only the two +different kinds of messages. Since our security model allows the messages to +be adversarially delayed and reordered, it is easy to show that the security +of an optimized, asymmetrical protocol is no worse than the symmetrical +version we present here. + + +\subsection{Security model and security definition} +\label{sec:um} + +Our model is very similar to that of Canetti and Krawczyk +\cite{Canetti:2001:AKE}, though we have modified it in two ways. +\begin{enumerate} +\item We allow all the participants (including the adversary) in the protocol + access to the various random oracles required to implement it. +\item Since we want to analyse a specific, practical scheme, asymptotic + results are useless. We measure the adversary's resource usage carefully, + and produce a quantitative bound on the adversary's advantage in the + SK-security game. +\end{enumerate} + +\ifshort + +Readers interested in the details of the model should see Canetti and +Krawczyk's paper \cite{Canetti:2001:AKE}, or the full version of this paper. + +\else + +\subsubsection{Overview} +We briefly describe our modified model, pointing out the changes we have +made, and how they apply to our protocol. Much of Canetti and Krawczyk's +model (for example, the local and global outputs) is useful for proving more +general security properties such as demonstrating that SK-security suffices +for constructing secure channels, and we shall not concern ourselves with +such details. Other parts deal with issues such as security parameters and +ensuring that all the computation is polynomially bounded, which are +irrelevant since we are dealing with a single concrete protocol rather than a +family of them. + +The entities in the model are the \emph{adversary}~$A$, and a (fixed) number +of \emph{parties}~$P_i$, for $0 \le i < n$. If the protocol under +consideration makes use of random oracles, then all the participants -- the +adversary and the parties -- are all allowed access to the random oracles. + +The parties and the adversary play a `game'. At the beginning of the game, +the participants are given some inputs computed by a randomized +\emph{initialization procedure}~$\id{init}$. This produces as output a pair +$(i_U, \mathbf{i})$; the value $i_U$ is the \emph{global input}, and is given +to all the participants including the adversary. The vector $\mathbf{i}$ has +$n$ components, and party $P_i$ is given $(i_U, \mathbf{i}[i])$ as input. + +\subsubsection{Sessions} +Parties don't act directly. Instead, each party runs a number of +\emph{sessions}. A session is represented by a triple $S = (P_i, P_j, s)$, +where $i, j \in \Nupto{n}$ identify the owning party and a \emph{partner}, +and $s \in \Bin^{\ell_S}$ is a \emph{session-id}. (The original model +includes a r\^ole, for distinguishing between initiators and responders. Our +protocol is symmetrical, so this distinction isn't useful.) If $P_i$ runs a +session $S = (P_i, P_j, s)$ and $P_j$ runs a session $S' = (P_j, P_i, s)$ +then we say that $S$ and $S'$ are \emph{matching}, and that $P_j$ is $P_i$'s +\emph{partner} for the session. + +At most one participant in the game is \emph{active} at any given time. +Initially the adversary is active. The adversary may \emph{activate} a +session in one of two ways. +\begin{enumerate} +\item It may \emph{create a session} of a party~$P_i$, by selecting a + session-id~$s \in \Bin^{\ell_S}$ and a partner $j$. There is no + requirement that $P_j$ ever have a matching session. However, all sessions + of a party must be distinct, i.e., sessions with the same partner must have + different session-ids. +\item It may \emph{deliver a message}~$\mu \in \Bin^*$, from party~$P_j$, to + an existing session~$S = (P_i, P_j, s)$. There is no requirement that any + party previously sent $\mu$: the adversary is free to make up messages as + it sees fit. +\end{enumerate} +The adversary becomes inactive, and the session becomes active. The session +performs some computation, according to its protocol, and may request a +message~$\mu$ be delivered to the matching session running in its partner +(which may not exist). The session may also \emph{terminate}. In the case +we are interested in, of key-exchange protocols, a session~$S = (P_i, P_j, +s)$ may terminate in one of two ways: +\begin{enumerate} +\item it may \emph{complete}, outputting $(i, j, s, K)$, for some + \emph{session key}~$K$, or +\item it may \emph{abort}, outputting $(i, j, s, \bot)$. +\end{enumerate} +Once it has performed these actions, the session deactivates and the +adversary becomes active again. The adversary is given the message~$\mu$, if +any, and informed of whether the session completed or aborted, but, in the +case of completion, not of the value of the key~$K$. A session is +\emph{running} if it has been created and has not yet terminated. + +\subsubsection{Other adversarial actions} +As well as activating sessions, the adversary has other capabilities, as +follows. +\begin{itemize} +\item It may \emph{expire} any session~$S$, causing the owning party to + `forget' the session key output by that session. +\item It may \emph{corrupt} any party~$P_i$, at will: the adversary learns + the entire state of the corrupted party, including its initial + input~$\mathbf{i}[i]$, the state of any sessions it was running at the + time, and the session keys of any completed but unexpired sessions. Once + corrupted, a party can no longer be activated. Of course, the adversary + can continue to send messages allegedly from the corrupted party. +\item It may \emph{reveal the state} of a running session~$S$, learning any + interesting values specific to that session, but \emph{not} the owning + party's long-term secrets. +\item It may \emph{reveal the session-key} of a completed session~$S$. +\item It may elect to be \emph{challenged} with a completed session~$S$, + provided. Challenge sessions form part of the security notion for + key-exchange protocols. See below for more details. +\end{itemize} +We say that a session $S = (P_i, P_j, s)$ is \emph{locally exposed} if +\begin{itemize} +\item it has had its state revealed, +\item it has had its session-key revealed, or +\item $P_i$ has been corrupted, and $S$ had not been expired when this + happened. +\end{itemize} +A session is \emph{exposed} if it is locally exposed, or if its matching +session exists and has been locally exposed. + +At the beginning of the game, a bit $b^*$ is chosen at random. The adversary +may choose to be \emph{challenged} with any completed, unexposed +session;\footnote{% + The original Canetti-Krawczyk definition restricts the adversary to a + single challenge session, but our proof works independent of the number of + challenge sessions, so we get a stronger result by relaxing the requirement + here.)} +the adversary is then given either the session's key -- if $b^* = 1$ -- or a +string chosen at random and independently of the game so far from a +protocol-specific distribution -- if $b^* = 0$. At the end of the game, the +adversary outputs a single bit~$b$. + +\subsubsection{SK-security} +We've now described the game; it is time to explain the adversary's goal in +it. The adversary \emph{wins} the game if either +\begin{enumerate} +\item two unexposed, matching sessions complete, but output different + keys,\footnote{% + The original Canetti-Krawczyk definition differs slightly here. It + requires that `if two \emph{uncorrupted} parties complete matching + sessions then they both output the same key' [original emphasis]. This + can't be taken at face value, since none of the protocols they claim to + be secure actually meet this requirement: they meet only the weaker + requirement that parties completing matching sessions output different + keys with negligible probability. We assume here that this is what they + meant.} + or +\item the adversary correctly guesses the hidden bit~$b^*$. +\end{enumerate} +More formally, we make the following definition. +\fi +\begin{definition}[SK-security] + \label{def:sk} + Let $\Pi^{H_0(\cdot), H_1(\cdot), \ldots}$ be a key-exchange protocol + which makes use of random oracles $H_0(\cdot)$, $H_1(\cdot)$, \dots, and + let $A$ be an adversary playing the game described \ifshort in + \cite{Canetti:2001:AKE}\else previously\fi, where $n$ + parties run the protocol~$\Pi$. Let $V$ be the event that any pair of + matching, unexposed sessions completed, but output different session keys. + Let $W$ be the event that the adversary's output bit matches the game's + hidden bit~$b^*$. We define the adversary's \emph{advantage against the + SK-security of the protocol~$\Pi$} to be + \[ \Adv{sk}{\Pi}(A, n) = \max(\Pr[V], 2\Pr[W] - 1). \] + Furthermore, we define the \emph{SK insecurity function of the + protocol~$\Pi$} to be + \[ \InSec{sk}(\Pi; t, n, q_S, q_M, q_{H_0}, q_{H_1}, \dots) = + \max_A \Adv{sk}{\Pi}(A, n) + \] + where the maximum is taken over all adversaries~$A$ with total running + time~$t$ (not including time taken by the parties), create at most $q_S$ + sessions, deliver at most $q_M$~messages, and (if applicable) make at most + $q_{H_i}$ random-oracle queries to each random oracle $H_i(\cdot)$. +\end{definition} + + +\subsection{Security} + +In order to analyse our protocol $\Wkx^{G, \E}$ properly, we must describe +exactly how it fits into our formal model. + +\subsubsection{Sessions and session-ids} +Our formal model introduced the concept of sessions, which the informal +description of section~\ref{sec:kx-overview} neglected to do. (One could +argue that we described a single session only.) As we shall show in +section~\ref{sec:kx-insecure}, our protocol is \emph{insecure} unless we +carefully modify it to distinguish between multiple sessions. + +In the model, distinct key-exchange sessions are given distinct partners and +session-ids. In order to prevent sessions interfering with each other, we +shall make explicit use of the session-ids. + +Suppose the session-ids are $\ell_S$-bit strings. We expand the domain of +the random oracle $H_I$ so that it's now +\[ H_I\colon G \times \Bin^{\ell_S} \times G \times G \to \Bin_{\ell_I}. \] + +\subsubsection{Messages} +We split the messages our protocols into two parts: a \emph{type}~$\tau$ and +a \emph{body}~$\mu$. We assume some convenient, unambiguous encoding of +pairs $(\tau, \mu)$ as bit-strings. For readability, we present message +types as text strings, e.g., `\cookie{challenge}', though in practice one +could use numerical codes instead. + +The message body itself may be a tuple of values, which, again, we assume are +encoded as bit-strings in some convenient and unambiguous fashion. We shall +abuse the notation for the sake of readability by dropping a layer of nesting +in this case: for example, we write $(\cookie{hello}, x, y, z)$ rather than +$\bigl(\cookie{hello}, (x, y, z)\bigr)$. + +\subsubsection{The protocol} +Our protocol is represented by three functions, shown in +figure~\ref{fig:wkx-formal}. +\begin{itemize} +\item $\id{init}(n)$ is the initialization function, as described in + section~\ref{sec:um}. It outputs a pair $(\mathbf{p}, \mathbf{i})$, where + $\mathbf{i}[i]$ is the private key of party~$P_i$ and $\mathbf{p}[i]$ is + the corresponding public key. Only $P_i$ is given $\mathbf{i}[i]$, whereas + all parties and the adversary are given $\mathbf{p}$. +\item $\id{new-session}^{H_I(\cdot, \cdot, \cdot, \cdot), H_K(\cdot)} + (\mathbf{p}, x, i, j, s)$ is the new-session function. This is executed by + party~$P_i$ when the adversary decides to create a new session~$S = (P_i, + P_j, s)$. It is also given the relevant outputs of $\id{init}$, and + allowed access to the random oracles $H_I$ and $H_K$. +\item $\id{message}^{H_I(\cdot, \cdot, \cdot, \cdot), H_K(\cdot)} (\tau, + \mu)$ is the incoming-message function. This is executed by a session when + the adversary decides to deliver a message $(\tau, \mu)$ to it. It makes + use of the subsidiary functions $\id{msg-challenge}$ and + $\id{msg-response}$ to handle the messages. +\end{itemize} +We observe that the protocol never aborts. We could make it do so if it +receives an invalid message, but we prefer to ignore invalid messages for the +sake of robustness.\footnote{% + Note that this protocol would therefore require modification before it was + acceptable in the simulation-based model of \cite{cryptoeprint:1999:012}. + There it is required that a key-exchange protocol terminate after a + polynomially-bounded number of messages are delivered to it.} + +\begin{figure} \begin{program} - Algorithm $\Xid{E}{CBC}^P_K(x)$: \+ \\ - $I \getsr \Bin^\ell$; \\ - $y \gets I$; \\ - \FOR $i = 0$ \TO $|x|/\ell$ \DO \\ \ind - $x_i \gets x[\ell i \bitsto \ell (i + 1)]$; \\ - $y_i \gets P_K(x_i \xor I)$; \\ - $I \gets y_i$; \\ - $y \gets y \cat y_i$; \- \\ - \RETURN $y$; + Function $\id{init}(n)$: \+ \\ + \FOR $i \in \Nupto{n}$ \DO \\ \ind + $x \getsr \gf{q}$; \\ + $\mathbf{i}[i] \gets x$; \\ + $\mathbf{p}[i] \gets x P$; \- \\ + \RETURN $(\mathbf{p}, \mathbf{i})$; + \- \\[\medskipamount] + Function $\id{new-session}^{H_I(\cdot, \cdot, \cdot, \cdot), H_K(\cdot)} + (\mathbf{p}, x, i, j, s)$: \+ \\ + $X \gets \mathbf{p}[i]$; + $X' \gets \mathbf{p}[j]$; + $C \gets \emptyset$; \\ + $r \getsr \gf{q}$; + $R \gets r P$; + $Y \gets r X'$; \\ + $h \gets H_I(X, s, R, Y)$; + $c \gets r \xor h$; \\ + \SEND $(\cookie{challenge}, R, c)$; + \- \\[\medskipamount] + Function $\id{message}^{H_I(\cdot, \cdot, \cdot, \cdot), H_K(\cdot)} + (\tau, \mu)$: \+ \\ + \IF $\tau = \cookie{challenge}$ \THEN $\id{msg-challenge}(\mu)$; \\ + \ELSE \IF $\tau = \cookie{response}$ \THEN $\id{msg-response}(\mu)$; \next - Algorithm $\Xid{D}{CBC}^P_K(y)$: \+ \\ - $I \gets y[0 \bitsto \ell]$; \\ - $x \gets \emptystring$; \\ - \FOR $1 = 0$ \TO $|y|/\ell$ \DO \\ \ind - $y_i \gets y[\ell i \bitsto \ell (i + 1)]$; \\ - $x_i \gets P^{-1}_K(y_i) \xor I$; \\ - $I \gets y_i$; \\ - $x \gets x \cat x_i$; \- \\ - \RETURN $x$; + Function $\id{msg-challenge}(\mu)$: \+ \\ + $(R', c') \gets \mu$; \\ + $Y' \gets x R'$; \\ + $h' \gets H_I(X', s, R', Y')$; \\ + $r' \gets c' \xor h'$; \\ + \IF $R' \ne r' P$ \THEN \RETURN; \\ + $C \gets C \cup \{R\}$; \\ + $Z \gets r R'$; \\ + $(K_0, K_1) \gets H_K(Z)$; \\ + $\chi \gets E_{K_0}(Y')$; \\ + \SEND $(\cookie{response}, R, \chi)$; + \- \\[\medskipamount] + Function $\id{msg-response}(\mu)$: \+ \\ + $(R', \chi') \gets \mu$; \\ + \IF $R' \notin C$ \THEN \RETURN; \\ + $Z \gets r R'$; \\ + $(K_0, K_1) \gets H_K(Z)$; \\ + $Y' \gets D_{K_0}(\chi')$; \\ + \IF $Y' \ne Y$ \THEN \RETURN; \\ + \OUTPUT $K_1$; + \STOP; \end{program} -\end{definition} -\begin{theorem}[Security of standard CBC mode] - \label{thm:cbc} - Let $P\colon \keys P \times \Bin^\ell \to \Bin^\ell$ be a pseudorandom - permutation. Then, - \begin{equation} - \InSec{lor-cpa}(\Xid{\mathcal{E}}{CBC}; t, q_E + \mu_E) \le - 2 \cdot \InSec{prp}(P; t + q t_P, q) + - \frac{q (q - 1)}{2^\ell - 2^{\ell/2}} - \end{equation} - where $q = \mu_E/\ell$ and $t_P$ is some small constant. + \caption{Formalization of $\Wkx$} + \label{fig:wkx-formal} +\end{figure} + +\subsubsection{Session states} +We must specify what the adversary obtains when it chooses to reveal a +session's state. Given the program in figure~\ref{fig:wkx-formal}, we can +see that the session state consists of the variables $(x, X, X', r, R, Y, +C)$. + +However, $x$ is the owning party's long-term secret, and it seems +unreasonable to disclose this to an adversary who stops short of total +corruption. + +The public keys $X$ and $X'$ are part of the adversary's input anyway, so +revealing them doesn't help. Similarly, the set $C$ of valid challenges +could have been computed easily by the adversary, since a group element $R' +\in C$ if and only if the session $S$ responded to some message +$(\cookie{challenge}, R', c')$. + +The value $R = r P$ is easily computed given $r$, and besides is sent in the +clear in the session's first message. The expected response $Y = r X'$ is +also easily computed from $r$. The converse is also true, since $r$ can be +recovered from $R$ and $c$ in the session's challenge message and the value +$Y$. Besides, $r$ is necessary for computing $Z$ in response to incoming +challenges. + +We conclude that the only `interesting' session state is $r$. + +\subsubsection{Security} +Having formally presented the protocol, we can now state our main theorem +about its security. The proof is given in \ifshort the full version of the +paper\else appendix~\ref{sec:sk-proof}\fi. +\begin{theorem}[SK-security of $\Wkx$] + \label{thm:sk} + Let $G$ be a cyclic group. Let $\E = (\kappa, E, D)$ be a symmetric + encryption scheme. Then + \begin{spliteqn*} + \InSec{sk}(\Wkx^{G, \E}; t, n, q_S, q_M, q_I, q_K) \le + 2 q_S \bigl( \InSec{ind-cca}(\E; t', q_M, q_M) + {} \\ + \InSec{mcdh}(G; t', q_K) + + n \,\InSec{mcdh}(G; t', q_M + q_I) \bigr) + + \frac{n (n - 1)}{q} + + \frac{2 q_M}{2^{\ell_I}}. + \end{spliteqn*} + where $t' = t + O(n) + O(q_S) + O(q_M q_I) + O(q_K)$. \end{theorem} -\begin{note} - Our security bound is slightly better than that of \cite[theorem - 17]{Bellare:2000:CST}. Their theorem statement contains a term $3 \cdot q - (q - 1) 2^{-\ell-1}$. Our result lowers the factor from 3 to just over 2. - Our proof is also much shorter and considerably more comprehensible. -\end{note} -The proof of this theorem is given in section~\ref{sec:cbc-proof} +\ifshort\else +\subsection{Insecure protocol variants} +\label{sec:kx-insecure} + +It's important to feed the session-id and verifier's public key to the random +oracle $H_I$ when constructing the check-value~$c$. Without these, the +protocol is vulnerable to attack. In this section, we consider some variants +of our protocol which hash less information, and show attacks against them. + +To simplify the presentation, we shall consider Alice and Bob, and a third +character Carol. We shall be attacking a pair of matching sessions $A$ +and~$B$, run by Alice and Bob respectively. Let Alice and Bob's private keys +be $x_A$ and~$x_B$, and let their public keys be $X_A = x_A P$ and $X_B = x_B +P$ respectively. + +\subsubsection{Protocol diagram notation} +In order to keep the presentation as clear as possible, we use a simple +diagrammatic notation for describing protocol runs. A line of the form +\protocolrun{\textit{action} \ar[r] & \PRsession{S} & \textit{result}} +states that the adversary performs the given \textit{action} on session~$S$, +with the stated \textit{result}. The \textit{action} may be +\begin{itemize} +\item \textsf{Create session $(P_i, P_j, s)$}: the session is created, + running in party~$P_i$, with partner~$P_j$ and session-id~$s$. +\item \textsf{Receive $\mu$}: the session is activated with an incoming message~$\mu$. +\item \textsf{Session-state reveal}: The adversary requests the session's + internal state. +\end{itemize} +The \textit{result} may be +\begin{itemize} +\item \textsf{Send $\mu'$}: the session requests the delivery of the + message~$\mu'$. +\item \textsf{Complete: $K$}: the session completes, outputting the key~$K$. +\item \textsf{State: $\sigma$}: the session's state is revealed to + be~$\sigma$. +\item \textsf{(Ignore)}: the result of the action is unimportant. +\end{itemize} -\subsection{Ciphertext stealing} +\subsubsection{Omitting the session-id} +Consider a protocol variant where session $S$ sets $h_S = H_I(X_N, R_S, +Y_S)$, where $N$ is the session's partner. That is, we've omitted the +session-id from the hash. An adversary can cross over two sessions between +Alice and Bob. Here's how. + +The attack assumes that Alice and Bob set up two pairs of matching sessions +with each other, thus. +\protocolrun{ + \PRcreate{Alice}{Bob}{s} & \PRsession{A} & + \PRsend{challenge}{R_A, c_A} \\ + \PRcreate{Bob}{Alice}{s} & \PRsession{B} & + \PRsend{challenge}{R_B, c_B} \\ + \PRcreate{Alice}{Bob}{s'} & \PRsession{A'} & + \PRsend{challenge}{R_{A'}, c_{A'}} \\ + \PRcreate{Bob}{Alice}{s'} & \PRsession{B'} & + \PRsend{challenge}{R_{B'}, c_{B'}} +} +Observe that the session pairs use distinct session-ids $s \ne s'$, so this +is allowed. Now the adversary crosses over the challenges, using the second +pair of sessions to provide responses to the challenges issued by the first +pair. By revealing the state in the second pair of sessions, the adversary +can work out the (probably different) session keys accepted by the first +pair. +\protocolrun{ + \PRreceive{challenge}{R_B, c_B} & \PRsession{A'} & + \PRsend{response}{R_{A'}, E_{K_{A'B,0}}(x_A R_B)} \\ + \PRreceive{challenge}{R_A, c_A} & \PRsession{B'} & + \PRsend{response}{R_{B'}, E_{K_{B'A,0}}(x_B R_A)} \\ + \PRreceive{challenge}{R_{A'}, c_{A'}} & \PRsession{A} & \PRignore \\ + \PRreceive{challenge}{R_{B'}, c_{B'}} & \PRsession{B} & \PRignore \\ + \PRreveal & \PRsession{A'} & r_{A'} \\ + \PRreveal & \PRsession{B'} & r_{B'} \\ + \PRreceive{response}{R_{B'}, E_{K_{B'A,0}}(x_B R_A)} & \PRsession{A} & + \PRcomplete{K_{AB',1}} \\ + \PRreceive{response}{R_{A'}, E_{K_{A'B,0}}(x_A R_B)} & \PRsession{B} & + \PRcomplete{K_{BA',1}} \\ +} +The adversary can now compute $K_{AB'} = H_K(r_{B'} R_A)$ and $K_{B'A} = +H_K(r_{A'} R_B)$. Safely in possession of both keys, the adversary can now +read and impersonate freely. + +\subsubsection{Omitting the partner's public key} +Now consider a protocol variant where session $S$ sets $h_S = H_I(s, R_S, +Y_S)$, where $s$ is the session-id. An adversary can use a sessions with +Carol to attack a session between Alice and Bob. Here's how the sessions are +set up. +\protocolrun{ + \PRcreate{Alice}{Bob}{s} & \PRsession{A} & + \PRsend{challenge}{R_A, c_A} \\ + \PRcreate{Bob}{Alice}{s} & \PRsession{B} & + \PRsend{challenge}{R_B, c_B} \\ + \PRcreate{Alice}{Carol}{s} & \PRsession{A'} & + \PRsend{challenge}{R_{A'}, c_{A'}} \\ + \PRcreate{Bob}{Carol}{s} & \PRsession{B'} & + \PRsend{challenge}{R_{B'}, c_{B'}} +} +Although each of Alice and Bob have two sessions with session-id~$s$, this is +allowed, since they are with different partners. The rest of the attack in +fact proceeds identically to the previous case. +\fi -Ciphertext stealing allows us to encrypt any message in $\Bin^*$ and make the -ciphertext exactly $\ell$ bits longer than the plaintext. See -figure~\ref{fig:cbc-steal} for a diagram. +\subsection{Deniability} +\label{sec:denial} + +We have claimed that the Wrestlers key-exchange protocol is \emph{deniable}. +In this section, we define what we mean, explain the limits of the +deniablility of the protocol as currently presented, fix the protocol with an +additional pass (which can be collapsed to a single message flow by breaking +the protocol's symmetry), and prove the deniability of the resulting +protocol. + +Our notion of deniability is taken from Di~Raimondo, Gennaro and Krawczyk +\cite{cryptoeprint:2006:280}, except that, as usual, we opt for a concrete +security approach. + +\subsubsection{Discussion} +Our definition for deniability is that, for any adversary interacting with +participants in the protocol, a simulator exists which can compute the same +things as the adversary. In particular, since an adversary could output a +transcript of the interactions between itself and the parties, it would +follow that a simulator could do this too. If the simulator is effective, +its output is indistinguishable from that of the real adversary, and hence no +`judge' (distinguisher) should be persuaded by evidence presented by someone +who claims to have witnessed or participated in an interaction. + +We work again the model described in~\ref{sec:um}. That is, our adversary +has complete control over the ordering and delivery of all messages. The +adversary is also able, at any time, to reveal the state of any session. +However, deniability is obviously impossible against an adversary who can +\emph{corrupt} other parties, since simulating such an adversary's actions +would necessarily require the simulator to compute private keys corresponding +to the known public keys, and this is (we believe) difficult, because an +efficient algorithm for doing this could easily attack our protocol, which we +already proved secure. Therefore, we forbid the adversary from corrupting +parties. + +In order to allow the adversary to participate in the protocol, rather than +merely observing it, we need to give it one or more private keys. We could +modify the initialization function \id{init} from figure~\ref{fig:wkx-formal} +to give the adversary a private key, but there's an easier way: we can just +give the adversary a number of private keys in its auxiliary input. + +\subsubsection{Definitions} +Let $\Pi$ be a key-exchange protocol, in the model described in +section~\ref{sec:um}. We use the simulation framework of +section~\ref{sec:sim}. We define the initialization function $I_\Pi$ to be +the initialization function of $\Pi$, as before, and the corresponding +world~$W_\Pi(\iota, \sigma, \tau, \mu)$ is a fairly straightforward mapping +of the adversary's possible actions to the simulation model: +\begin{itemize} +\item The invocation $\cookie{new-session}$ with $\mu = (i, j, s)$ creates a + new session on party~$P_i$, with partner~$P_j$ and session-id~$s$. The + reply $\rho = (\delta, m)$ is a \emph{decision} $\delta \in + \{\cookie{continue}, \cookie{abort}, \cookie{complete}\}$ and an output + message $m \in \Bin^* \cup \{\bot\}$. If $m \ne \bot$ then $m$ is a + message to be sent to the matching session (if any). +\item The invocation $\cookie{deliver}$ with $\mu = (i, j, s, m)$ delivers + message $m$ to the session $S = (P_i, P_j, s)$. The response $\rho$ is as + for $\cookie{new-session}$ invocations. +\item The invocation $\cookie{reveal-session-state}$ with $\mu = (i, j, s)$ + reveals to the adversary the state of the running session $S = (P_i, P_j, + s)$. The response $\rho$ is the session's state if $S$ is indeed a running + session, or $\bot$ otherwise. +\item The invocation $\cookie{reveal-session-key}$ with $\mu = (i, j, s)$ + reveals to the adversary the session-key of the completed session~$S = + (P_i, P_j, s)$. The response $\rho$ is the session key~$K$ if the session + is indeed complete, or $\bot$ otherwise. +\end{itemize} +There are no invocations corresponding to the adversary actions of corrupting +parties (since deniability against an corrupting adversary is impossible, as +discussed earlier), or session expiry or challenging (since they are useless +in this context). + +We measure the deniability of a protocol~$\Pi$, using a given simulator~$S$, +by the insecurity function $\InSec{sim}(W_\Pi, I_\Pi, S; t_D, t_A, +\mathcal{Q}_D, \mathcal{Q}_A, \mathcal{R}, \mathcal{U})$ of +definition~\ref{def:sim}. The interaction bounds $\mathcal{R} = (q_S, q_M)$ +we place on the adversary are on the number ($q_S$) of \cookie{new-session} +and ($q_M$) \cookie{deliver} invocations it makes. + +We shall (informally) say that a protocol~$\Pi$ is deniable if there is a +simulator~$S_\Pi$ for which the insecurity function is small for appropriate +resource bounds on the adversary and distinguisher. + +\subsubsection{The current protocol} +As it stands, $\Wkx$ isn't deniable, according to our definition, for +arbitrary auxiliary inputs. Let's see why. + +Suppose that Bob is an informant for the secret police, and wants to convince +a judge that Alice is involved in subversive activities in cyberspace. +Unfortunately, Bob's job is difficult, because of the strong zero-knowledge +nature of the Wrestlers identification protocol. However, Bob can work with +the judge to bring him the evidence necessary to convict Alice. Here's how. + +Alice's public key is $A$, and Bob's public key is $B$. The judge chooses +some session-id $s$, and $r \inr \gf{q}$. He computes $R = r P$ and $c = +r \xor H_I(B, s, R, r A)$, and gives Bob the triple $(s, R, c)$, keeping $r$ +secret. Bob can now persuade Alice to enter into a key-exchange with him, +with session-id $s$. He uses $(R, c)$ as his challenge message. When Alice +sends back her response $(R', \chi)$ (because Bob's challenge is correctly +formed), Bob aborts and shows $(R', \chi)$ to the judge. The judge knows $r$ +and can therefore decrypt $\chi$ and check the response. If it's wrong, then +Bob was cheating and gets demoted -- he can't get the right answer by himself +because that would require him to impersonate Alice. If it's right, Alice is +really a subversive element and `disappears' in the night. + +We shall show in theorem~\ref{thm:denial} below that this is basically the +only attack against the deniability of the protocol. However, we can do +better. + +\subsubsection{Fixing deniability} +We can fix the protocol to remove even the attack discussed above. The +change is simple: we feed \emph{both} parties' challenges to the hash +function~$H_I$ rather than just the sender's. We use a five-argument hash +function (random oracle) $H_I\colon G^2 \times \Bin^{\ell_S} \times G^2 \to +\Bin^{\ell_I}$. We introduce a new message pass at the beginning of the +protocol: each session simply sends its challenge point $R = r P$ in the +clear as a `pre-challenge'. The actual challenge is $R$ and $c = r \xor +H_I(X, R', s, R, c)$, where $R'$ is the challenge of the matching session. + +By breaking symmetry, we can reduce the communication complexity of this +variant to four messages. As before, we analyse the symmetrical version. +The extra flow might seem a high price to pay, but we shall see that it has +additional benefits beyond deniability. + +A summary of the new protocol is shown in figure~\ref{fig:wdkx}, and the +formal description is shown in figure~\ref{fig:wdkx-formal}. \begin{figure} - \[ \begin{graph} - []!{0; <0.85cm, 0cm>: <0cm, 0.5cm>::} - *+=(1, 0)+[F]{\mathstrut x_0}="x" - :[dd] *{\xor}="xor" - [ll] *+=(1, 0)+[F]{I} :"xor" - :[dd] *+[F]{E}="e" :[ddddd] *+=(1, 0)+[F]{\mathstrut y_0}="i" - "e" [l] {K} :"e" - [rrruuuu] *+=(1, 0)+[F]{\mathstrut x_1}="x" - :[dd] *{\xor}="xor" - "e" [d] :`r [ru] `u "xor" "xor" - :[dd] *+[F]{E}="e" :[ddddd] - *+=(1, 0)+[F]{\mathstrut y_1}="i" - "e" [l] {K} :"e" - [rrruuuu] *+=(1, 0)+[F--]{\mathstrut x_i}="x" - :@{-->}[dd] *{\xor}="xor" - "e" [d] :@{-->}`r [ru] `u "xor" "xor" - :@{-->}[dd] *+[F]{E}="e" :@{-->}[ddddd] - *+=(1, 0)+[F--]{\mathstrut y_i}="i" - "e" [l] {K} :@{-->}"e" - [rrruuuu] *+=(1, 0)+[F]{\mathstrut x_{n-2}}="x" - :[dd] *{\xor}="xor" - "e" [d] :@{-->}`r [ru] `u "xor" "xor" - :[dd] *+[F]{E}="e" - "e" [l] {K} :"e" - [rrruuuu] *+=(1, 0)+[F]{\mathstrut x_{n-1} \cat 0^{\ell-t}}="x" - :[dd] *{\xor}="xor" - "e" [d] :`r [ru] `u "xor" "xor" - "e" [dddddrrr] *+=(1, 0)+[F]{\mathstrut y_{n-1}[0 \bitsto t]}="i" - "e" [dd] ="x" - "i" [uu] ="y" - []!{"x"; "e" **{}, "x"+/4pt/ ="p", - "x"; "y" **{}, "x"+/4pt/ ="q", - "y"; "x" **{}, "y"+/4pt/ ="r", - "y"; "i" **{}, "y"+/4pt/ ="s", - "e"; - "p" **\dir{-}; - "q" **\crv{"x"}; - "r" **\dir{-}; - "s" **\crv{"y"}; - "i" **\dir{-}?>*\dir{>}} - "xor" :[dd] *+[F]{E}="e" - "e" [l] {K} :"e" - "e" [dddddlll] *+=(1, 0)+[F]{\mathstrut y_{n-2}}="i" - "e" [dd] ="x" - "i" [uu] ="y" - []!{"x"; "e" **{}, "x"+/4pt/ ="p", - "x"; "y" **{}, "x"+/4pt/ ="q", - "y"; "x" **{}, "y"+/4pt/ ="r", - "y"; "i" **{}, "y"+/4pt/ ="s", - "x"; "y" **{} ?="c" ?(0.5)/-4pt/ ="cx" ?(0.5)/4pt/ ="cy", - "e"; - "p" **\dir{-}; - "q" **\crv{"x"}; - "cx" **\dir{-}; - "c" *[@]\cir<4pt>{d^u}; - "cy"; - "r" **\dir{-}; - "s" **\crv{"y"}; - "i" **\dir{-}?>*\dir{>}} - \end{graph} \] - - \caption{Encryption using CBC mode with ciphertext stealing} - \label{fig:cbc-steal} + \begin{description} + \item[Setup] Group $G = \langle P \rangle$; $\#G = q$ is prime. + $H_I(\cdot, \cdot, \cdot, \cdot, \cdot)$ and $H_K(cdot)$ are secure + hashes. $\E = (\kappa, E, D)$ is an IND-CCA2 symmetric encryption + scheme. + \item[Parties] $U_i$ for $0 \le i < n$. + \item[Private keys] $x_i \inr \gf{q}$. + \item[Public keys] $X_i = x_i P$. + \end{description} + + \begin{protocol} + $r_i \getsr I$; $R_i \gets r_i P$; & + $r_j \getsr I$; $R_j \gets r_j P$; \\ + \send{->}{R_i} + \send{<-}{R_j} + $c_i \gets r_i \xor H_I(R_j, X_i, s, R_i, r_i X_j)$; & + $c_j \gets r_j \xor H_I(R_i, X_j, s, R_j, r_j X_i)$; \\ + \send{->}{(R_i, c_i)} + \send{<-}{(R_j, c_j)} + Check $R_j = \bigl(c_j \xor H_I(x_i R_j)\bigr) P$; & + Check $R_i = \bigl(c_i \xor H_I(x_j R_i)\bigr) P$; \\ + $Z \gets r_i R_j$; $(K_0, K_1) \gets H_K(Z)$; & + $Z \gets r_j R_i$; $(K_0, K_1) \gets H_K(Z)$; \\ + $\chi_i \gets E_{K_0}(x_i R_j)$; & + $\chi_j \gets E_{K_0}(x_j R_i)$; \\ + \send{->}{(R_i, \chi_i)} + \send{<-}{(R_j, \chi_j)} + Check $D_{K_0}(\chi_j) = r_i X_j$; & + Check $D_{K_0}(\chi_i) = r_j X_i$; \\ + Shared key is $K_1$. & Shared key is $K_1$. + \end{protocol} + + \caption{Summary of the Deniable Wrestlers Key Exchange protocol, $\Wdkx$} + \label{fig:wdkx} \end{figure} -\begin{definition}[CBC stealing] - \label{def:cbc-steal} - Let $P\colon \keys P \times \Bin^\ell \to \Bin^\ell$ be a pseudorandom - permutation. We define the symmetric encryption scheme - $\Xid{\mathcal{E}}{CBC-steal}^P = (\Xid{G}{CBC}^P, \Xid{E}{CBC-steal}^P, - \Xid{D}{CBC-steal}^P)$ for messages in $\Bin^{\ell\Z}$ by setting $\keys - \Xid{\mathcal{E}}{CBC-steal} = \keys P$ and defining the encryption and - decryption algorithms as follows: +\begin{figure} \begin{program} - Algorithm $\Xid{E}{CBC-steal}^P_K(x)$: \+ \\ - $I \getsr \Bin^\ell$; \\ - $y \gets I$; \\ - $t = |x| \bmod \ell$; \\ - \IF $t \ne 0$ \THEN $x \gets x \cat 0^{\ell-t}$; \\ - \FOR $i = 0$ \TO $|x|/\ell$ \DO \\ \ind - $x_i \gets x[\ell i \bitsto \ell (i + 1)]$; \\ - $y_i \gets P_K(x_i \xor I)$; \\ - $I \gets y_i$; \\ - $y \gets y \cat y_i$; \- \\ - \IF $t \ne 0$ \THEN \\ \ind - $b \gets |y| - 2\ell$; \\ - $y \gets $\=$y[0 \bitsto b] \cat - y[b + \ell \bitsto |y|] \cat {}$ \\ - \>$y[b \bitsto b + t]$; \- \\ - \RETURN $y$; + Function $\id{init}(n)$: \+ \\ + \FOR $i \in \Nupto{n}$ \DO \\ \ind + $x \getsr \gf{q}$; \\ + $\mathbf{i}[i] \gets x$; \\ + $\mathbf{p}[i] \gets x P$; \- \\ + \RETURN $(\mathbf{p}, \mathbf{i})$; + \- \\[\medskipamount] + Function $\id{new-session}^{H_I(\cdot, \cdot, \cdot, \cdot, \cdot), H_K(\cdot)} + (\mathbf{p}, x, i, j, s)$: \+ \\ + $X \gets \mathbf{p}[i]$; + $X' \gets \mathbf{p}[j]$; + $C \gets \emptyset$; \\ + $r \getsr \gf{q}$; + $R \gets r P$; + $Y \gets r X'$; \\ + \SEND $(\cookie{pre-challange}, R)$; + \- \\[\medskipamount] + Function $\id{message}^{H_I(\cdot, \cdot, \cdot, \cdot, \cdot), H_K(\cdot)} + (\tau, \mu)$: \+ \\ + \IF $\tau = \cookie{pre-challenge}$ \THEN + $\id{msg-pre-challenge}(\mu)$; \\ + \ELSE \IF $\tau = \cookie{challenge}$ \THEN + $\id{msg-challenge}(\mu)$; \\ + \ELSE \IF $\tau = \cookie{response}$ \THEN $\id{msg-response}(\mu)$; \next - Algorithm $\Xid{D}{CBC-steal}^P_K(y)$: \+ \\ - $I \gets y[0 \bitsto \ell]$; \\ - $t = |y| \bmod \ell$; \\ - \IF $t \ne 0$ \THEN \\ \ind - $b \gets |y| - t - \ell$; \\ - $z \gets P^{-1}_K(y[b \bitsto b + \ell])$; \\ - $y \gets $\=$y[0 \bitsto b] \cat - y[b + \ell \bitsto |y|] \cat {}$ \\ - \>$z[t \bitsto \ell]$; \- \\ - $x \gets \emptystring$; \\ - \FOR $1 = 0$ \TO $|y|/\ell$ \DO \\ \ind - $y_i \gets y[\ell i \bitsto \ell (i + 1)]$; \\ - $x_i \gets P^{-1}_K(y_i) \xor I$; \\ - $I \gets y_i$; \\ - $x \gets x \cat x_i$; \- \\ - \IF $t \ne 0$ \THEN \\ \ind - $x \gets x \cat z[0 \bitsto t] \xor y[b \bitsto b + t]$; \- \\ - \RETURN $x$; + Function $\id{msg-pre-challenge}(\mu)$: \+ \\ + $R' \gets \mu$; \\ + $h \gets H_I(R', X, s, R, c)$; \\ + $c \gets r \xor h$; \\ + \SEND $(\id{msg-challenge}, R, c)$; + \- \\[\medskipamount] + Function $\id{msg-challenge}(\mu)$: \+ \\ + $(R', c') \gets \mu$; \\ + $Y' \gets x R'$; \\ + $h' \gets H_I(R, X', s, R', Y')$; \\ + $r' \gets c' \xor h'$; \\ + \IF $R' \ne r' P$ \THEN \RETURN; \\ + $C \gets C \cup \{R\}$; \\ + $Z \gets r R'$; \\ + $(K_0, K_1) \gets H_K(Z)$; \\ + $\chi \gets E_{K_0}(Y')$; \\ + \SEND $(\cookie{response}, R, \chi)$; + \- \\[\medskipamount] + Function $\id{msg-response}(\mu)$: \+ \\ + $(R', \chi') \gets \mu$; \\ + \IF $R' \notin C$ \THEN \RETURN; \\ + $Z \gets r R'$; \\ + $(K_0, K_1) \gets H_K(Z)$; \\ + $Y' \gets D_{K_0}(\chi')$; \\ + \IF $Y' \ne Y$ \THEN \RETURN; \\ + \OUTPUT $K_1$; + \STOP; \end{program} -\end{definition} -\begin{theorem}[Security of CBC with ciphertext stealing] - \label{thm:cbc-steal} - Let $P\colon \keys P \times \Bin^\ell \to \Bin^\ell$ be a pseudorandom - permutation. Then + \caption{Deniable key-exchange: formalization of $\Wdkx$} + \label{fig:wdkx-formal} +\end{figure} + +The security of this variant is given by the following theorem, whose proof +is \ifshort given in the full version of this paper\else in +appendix~\ref{sec:sk2-proof}\fi. +\begin{theorem}[SK-security of $\Wdkx$] + \label{thm:sk2} + Let $G$ be a cyclic group. Let $\E = (\kappa, E, D)$ be a symmetric + encryption scheme. Then + \[ \InSec{sk}(\Wdkx^{G, \E}; t, n, q_S, q_M, q_I, q_K) = + \InSec{sk}(\Wkx^{G, \E}; t, n, q_S, q_M, q_I, q_K) + \] +\end{theorem} + +\subsubsection{Deniability of the Wrestlers protocols} +In order to quantify the level of deniability our protocols provide, we shall +impose a limit on the auxiliary input to the adversary. In particular, we +shall use $\mathcal{U}$ of definition~\ref{def:sim} to count the number of +\emph{challenges} in the auxiliary input. That is, $\mathcal{U} = n_C$ is +the number of tuples $(i, j, s, R', R, c)$ for which there is an $r$ such +that $R = r P$ and $c = r \xor H_I(R', X_j, s, R, r X_i)$ (or without the +$R'$ for $\Wkx$). + +With this restriction in place, we can state the following theorem about the +deniability of our protocols. +\begin{theorem}[Deniability of $\Wkx$ and $\Wdkx$] + \label{thm:denial} + There exist simulators $S_\Wkx$ and $\Wdkx$ such that + \[ \InSec{sim}(W_{\Wkx^{G, \E}}, I_{\Wkx^{G, \E}}, S_{\Wkx^{G, \E}}; + t_D, t_A, \mathcal{Q}_D, \mathcal{Q}_A, (q_S, q_M), 0) \le + \frac{q_M}{2^{\ell_I}} + \] + and + \iffancystyle\[\else\begin{spliteqn*}\fi + \InSec{sim}(W_{\Wdkx^{G, \E}}, I_{\Wdkx^{G, \E}}, S_{\Wdkx^{G, \E}}; + t_D, t_A, \mathcal{Q}_D, \mathcal{Q}_A, (q_S, q_M), n_C) \le + \iffancystyle\else\\\fi + \frac{n_C q_S}{\#G} + + \frac{q_M}{2^{\ell_I}}. + \iffancystyle\]\else\end{spliteqn*}\fi + The running time of the simulators is $O(t_A) + O(\mathcal{Q}_A q_M)$. +\end{theorem} +\begin{longproof}{The proof of this theorem can be found in the full version + of this paper.} + The simulators $S_\Wkx$ and $S_\Wdkx$ are very similar. We describe both + here. Both are fake-world simulators, working as follows. + \begin{enumerate} + \item Initially, it constructs simulated parties $P_i$, for $0 \le i < n$, + giving each the public key $X_i$ from the common input. + \item Suppose the adversary requests creation of a new session $S = (P_i, + P_j, s)$. Then the simulator creates a new session, including a random + value $r_S \inr \gf{q}$, and computes $R_S = r_S P$, and $Y_S = r_S + X_j$. For $\Wdkx$, it sends the message $(\cookie{pre-challenge}, R_S)$; + for $\Wkx$, it additionally computes $h = H_I(X_i, s, R_S, Y_S)$ and + sends $(\cookie{challenge}, R_S, r_S \xor h)$. + \item Suppose, for $\Wdkx$, the adversary sends a message + $(\cookie{pre-challenge}, R')$ to a session~$S = (P_i, P_j, s)$. The + simulator computes $h = H_I(R', X_i, s, R_S, Y_S)$, and sends + $(\cookie{challenge}, R_S, r_S \xor h)$. + \item Suppose the adversary sends a message $(\cookie{challenge}, R', c')$ + to session $S = (P_i, P_j, s)$. The simulator doesn't know $x_i$. + \begin{enumerate} + \item If $R' = R_T$ for some other simulated session $T$, then the + simulator knows $r_T$ such that $R_T = r_T P$. Let $Y' = r_T X_i$. + The simulator computes $h = H_I(X_j, s, R', Y')$ (resp.\ $h = H_I(R_S, + X_j, s, R', Y')$) for $\Wkx$ (resp.\ $\Wdkx$) and checks that $r_T = c' + \xor h$. If not, the simulator discards the message. Otherwise, it + computes $(K_0, K_1) = H_K(r_S R')$, and sends the message + $(\cookie{response}, R, E_{K_0}(Y'))$. + \item \label{en:simextract} Otherwise the simulator runs the extractor + $T_\Wident$ on the adversary's history of queries $H_I(X_j, s, R', + \cdot)$ (resp.\ $H_I(R_S, X_j, s, R', \cdot)$) for $\Wkx$ (resp.\ + $\Wdkx$). The extractor returns $(r', Y')$. If $Y' = \bot$ then the + simulator ignores the message. Otherwise, the simulator computes + $(K_0, K_1) = H_K(r R')$ and sends back $(\cookie{response}, R, + E_{K_0}(Y'))$. + \end{enumerate} + \item Suppose the adversary sends a message $(\cookie{response}, R', \chi)$ + to session $S = (P_i, P_j, s)$. The simulator computes $(K_0, K_1) = + H_K(r_S R')$, and decrypts $Y' = D_{K_0}(\chi)$. If $Y' \ne Y_S$ then + the simulator discards the message. Otherwise, it makes the simulated + session complete, and outputs key $K_1$. + \item Finally, if the adversary reveals a session's state, the simulator + reveals $r_S$ as required; if the adversary reveals a session-key, the + simulator reveals the $K_1$ it output. + \end{enumerate} + The only point where the simulation fails to be perfect is in + \ref{en:simextract}. Let $R'$ and $c'$ be the values from an incoming + challenge message to session $S = (P_i, P_j, s)$. Let $r'$ be such that + $R' = r' P$ and let $Y' = r' X_i$. If a random-oracle query $H_I(X_j, s, + R', Y')$ (or $H_I(R_S, X_j, s, R', Y')$ for $\Wdkx$) has been issued, then + there are a number of possibilities. Let $h'$ be the result of this query. + \begin{itemize} + \item The adversary made this query. Then the extractor will find it and + return $Y'$ if $c' = h' \xor r'$, or $\bot$ otherwise. + \item Some simulated session $U = (P_{i'}, P_{j'}, s')$ made this query. + But simulated sessions only make $H_I$-queries when constructing + challenges, so $R' = R_U$ for some session~$U$. But the simulator does + something different in that case. + \item In $\Wdkx$, the quadruple $(s, R_S, R', c')$ came from the + adversary's auxiliary input. In this case the simulator must fail. But + $R_S = r_S P$, and $r_S$ was chosen uniformly at random. If there are at + most $n_C$ challenge sets in the auxiliary input then this happens with + probability at most $n_C/\#G$ for any given session. + \end{itemize} + We conclude that the simulator fails with probability + \[ \frac{q_M}{2^{\ell_I}} + \frac{q_S n_C}{\#G}. \] + (Note that we only consider $n_C = 0$ for $\Wkx$.) No adversary can + distinguish the simulator from a real interaction unless the simulator + fails, and the simulator is a fake-world simulator. We therefore apply + proposition~\ref{prop:fakesim}; the theorem follows. +\end{longproof} + +\ifshort\else +\subsection{Practical issues} +\label{sec:practice} + +\subsubsection{Denial of service from spoofers} +The adversary we considered in~\ref{sec:um} is very powerful. Proving +security against such a powerful adversary is good and useful. However, +there are other useful security properties we might like against weaker +adversaries. + +Eavesdropping on the Internet is actually nontrivial. One needs control of +one of the intermediate routers between two communicating parties. (There +are tricks one can play involving subversion of DNS servers, but this is also +nontrivial.) However, injecting packets with bogus source addresses is very +easy. + +Layering the protocol over TCP \cite{rfc793} ameliorates this problem because +an adversary needs to guess or eavesdrop in order to obtain the correct +sequence numbers for a spoofed packet; but the Wrestlers protocol is +sufficiently simple that we'd like to be able to run it over UDP +\cite{rfc768}, for which spoofing is trivial. + +Therefore, it's possible for anyone on the 'net to send Alice a spurious +challenge message $(R, c)$. She will then compute $Y = a R$, recover $r' = c +\xor H_I(\ldots, R, Y)$ check that $R = r' P$ and so on. That's at least two +scalar multiplications to respond to a spoofed packet, and even with very +efficient group operations, coping with this kind of simple denial-of-service +attack might be difficult. + +A straightforward solution is to use the Deniable variant of the protocol, +and require a challenge to quote its matching session's challenge $R'$ in its +challenge. That is, upon receiving a $(\cookie{pre-challenge}, R')$, the +session sends $(\cookie{challenge}, R', R, c)$. Alice then rejects any +\emph{incoming} challenge message which doesn't quote her current challenge +value. Now only eavesdroppers can force her to perform expensive +computations. + +Indeed, one need not quote the entire challenge $R'$: it suffices to send +some short hard-to-guess hash of it, maybe just the bottom 128 bits or so. + +This can't reduce security. Consider any adversary attacking this protocol +variant. We can construct an adversary which attacks the original protocol +just as efficiently. The new adversary attaches fake $R'$ values to +challenges output by other parties, and strips them off on delivery, +discarding messages with incorrect $R'$ values. + +\subsubsection{Key confirmation} +Consider an application which uses the Wrestlers protocol to re-exchange keys +periodically. The application can be willing to \emph{receive} incoming +messages using the new key as soon as the key exchange completes +successfully; however, it should refrain from \emph{sending} messages under +the new key until it knows that its partner has also completed. The partner +may not have received the final response message, and therefore be unwilling +to accept a new key; it will therefore (presumably) reject incoming messages +under this new key. + +While key confirmation is unnecessary for \emph{security}, it has +\emph{practical} value, since it solves the above problem. If the +application sends a \cookie{switch} message when it `completes', it can +signal its partner that it is indeed ready to accept messages under the new +key. Our implementation sends $(\cookie{switch-rq}, E_{K_0}(H_S(0, R, R')))$ +as its switch message; the exact contents aren't important. Our +retransmission policy (below) makes use of an additional message +\cookie{switch-ok}, which can be defined similarly. + +It's not hard to show that this doesn't adversely affect the security of the +protocol, since the encrypted message is computed only from public values. +In the security proof, we modify the generation of \cookie{response} +messages, so that the plaintexts are a constant string rather than the true +responses, guaranteeing that the messages give no information about the +actual response. To show this is unlikely to matter, we present an adversary +attacking the encryption scheme by encrypting either genuine responses or +fake constant strings. Since the adversary can't distinguish which is being +encrypted (by the definition of IND-CCA security, +definition~\ref{def:ind-cca}), the change goes unnoticed. In order to allow +incorporate our switch messages, we need only modify this adversary, to +implement the modified protocol. This is certainly possible, since the +messages contain (hashes of) public values. We omit the details. + +However, while the extra message doesn't affect the security of our protocol, +it would be annoying if an adversary could forge the switch request message, +since this would be a denial of service. In the strong adversarial model, +this doesn't matter, since the adversary can deny service anyway, but it's a +concern against less powerful adversaries. Most IND-CCA symmetric encryption +schemes also provide integrity of plaintexts \cite{Bellare:2000:AER} (e.g., +the encrypt-then-MAC generic composition approach \cite{Bellare:2000:AER,% +Krawczyk:2001:OEA}, and the authenticated-encryption modes of +\cite{Rogaway:2003:OBC,Bellare:2004:EAX,McGrew:2004:SPG}), so this isn't a +great imposition. + +\subsubsection{Optimization and piggybacking} +We can optimize the number of messages sent by combining them. Here's one +possible collection of combined messages: +\begin{description} +\item [\cookie{pre-challenge}] $R$ +\item [\cookie{challenge}] $R'$, $R$, $c = H_I(R', X, s, R, c) \xor r$ +\item [\cookie{response}] $R'$, $R$, $c$, $E_{K_0}(x R')$ +\item [\cookie{switch}] $R'$, $E_{K_0}(x R', H_S(0, R, R'))$ +\item [\cookie{switch-ok}] $R'$, $E_{K_0}(H_S(1, R, R'))$ +\end{description} +The combination is safe: +\begin{itemize} +\item the \cookie{switch} and \cookie{switch-ok} messages are safe by the + argument above; and +\item the other recombinations can be performed and undone in a `black box' + way, by an appropriately defined SK-security adversary. +\end{itemize} + +\subsubsection{Unreliable transports} +The Internet UDP \cite{rfc768} is a simple, unreliable protocol for +transmitting datagrams. However, it's very efficient, and rather attractive +as a transport for datagram-based applications such as virtual private +networks (VPNs). Since UDP is a best-effort rather than a reliable +transport, it can occasionally drop packets. Therefore it is necessary for a +UDP application to be able to retransmit messages which appear to have been +lost. + +We recommend the following simple retransmission policy for running the +Wrestlers protocol over UDP. +\begin{itemize} +\item Initially, send out the \cookie{pre-challenge} message every minute. +\item On receipt of a \cookie{pre-challenge} message, send the corresponding + full \cookie{challenge}, but don't retain any state. +\item On receipt of a (valid) \cookie{challenge}, record the challenge value + $R'$ in a table, together with $K = (K_0, K_1)$ and the response $Y' = x + R'$. If the table is full, overwrite an existing entry at random. Send + the corresponding \cookie{response} message, and retransmit it every ten + seconds or so. +\item On receipt of a (valid) \cookie{response}, discard any other + challenges, and stop sending \cookie{pre-challenge} and \cookie{response} + retransmits. At this point, the basic protocol described above would + \emph{accept}, so the key $K_1$ is known to be good. Send the + \cookie{switch} message, including its response to the (now known-good) + sender's challenge. +\item On receipt of a (valid) \cookie{switch}, send back a \cookie{switch-ok} + message and stop retransmissions. It is now safe to start sending messages + under $K_1$. +\item On receipt of a (valid) \cookie{switch-ok}, stop retransmissions. It + is now safe to start sending messages under $K_1$. +\end{itemize} + +\subsubsection{Key reuse} +Suppose our symmetric encryption scheme $\E$ is not only IND-CCA secure +(definition~\ref{def:ind-cca}) but also provides integrity of plaintexts +\cite{Bellare:2000:AER} (or, alternatively, is an AEAD scheme +\cite{Rogaway:2002:AEA}. Then we can use it to construct a secure channel, +by including message type and sequence number fields in the plaintexts, along +with the message body. If we do this, we can actually get away with just the +one key $K = H_K(Z)$ rather than both $K_0$ and $K_1$. + +To do this, it is essential that the plaintext messages (or additional data) +clearly distinguish between the messages sent as part of the key-exchange +protocol and messages sent over the `secure channel'. Otherwise, there is a +protocol-interference attack: an adversary can replay key-exchange +ciphertexts to insert the corresponding plaintexts into the channel. + +We offer a sketch proof of this claim in appendix~\ref{sec:sc-proof}. +\fi + +%%%-------------------------------------------------------------------------- + +\section{Conclusions} +\label{sec:conc} + +We have presented new protocols for identification and authenticated +key-exchange, and proven their security. We have shown them to be efficient +and simple. We have also shown that our key-exchange protocol is deniable. +Finally, we have shown how to modify the key-exchange protocol for practical +use, and proven that this modification is still secure. + +%%%-------------------------------------------------------------------------- + +\section{Acknowledgements} + +The Wrestlers Protocol is named after the Wrestlers pub in Cambridge where +Clive Jones and I worked out the initial design. + +%%%-------------------------------------------------------------------------- + +\bibliography{wrestlers} + +%%%-------------------------------------------------------------------------- + +\ifshort\def\next{\end{document}}\expandafter\next\fi +\appendix +\section{Proofs} + +\subsection{Proof of theorem~\ref{thm:sk}} +\label{sec:sk-proof} + +Before we embark on the proof proper, let us settle on some notation. Let +$P_i$ be a party. Then we write $x_i$ for $P_i$'s private key and $X_i = x_i +P$ is $P_i$'s public key. Let $S = (P_i, P_j, s)$ be a session. We write +$r_S$ for the random value chosen at the start of the session, and $R_S$, +$c_S$ etc.\ are the corresponding derived values in that session. + +The proof uses a sequence of games. For each game~$\G{i}$, let $V_i$ be the +event that some pair of unexposed, matching sessions both complete but output +different keys, and let $W_i$ be the event that the adversary's final output +equals the game's hidden bit~$b^*$. To save on repetition, let us write +\[ \diff{i}{j} = \max(|\Pr[V_i] - \Pr[V_j]|, |\Pr[W_i] - \Pr[W_j]|). \] +Obviously, +\[ \diff{i}{j} \le \sum_{i\le k 5$, we define the event $F_i$ to be the event + corresponding to $F_5$ in $\G{i}$. Note that if $S_k$ \emph{is} sent a + message in $M_{T_k}$ then $S_k$ immediately completes. + + \begin{claim} + $\Pr[F_4] \le \Pr[F_5]/q_S$. + \end{claim} + This claim is proven exactly as we did for claim~1 of + lemma~\ref{lem:sk-g2-g3}. + + Let~$\G6$ be the same as $\G5$ except that we change the encrypted + responses of session~$S_k$ and its matching session~$T_k$. Let $K^* = + (K_0^*, K_1^*) = H_K(Z_S)$. Then, rather than sending $(\cookie{response}, + R_S, E_{K_0^*}(Y_T))$, session~$S$ sends $(\cookie{response}, R_S, + E_{K_0^*}(1^{\ell_G}))$. + \begin{claim} + $|\Pr[F_6] - \Pr[F_5]| \le \InSec{ind-cca}(\E; t', q_M, q_M).$ + \end{claim} + To prove this claim, we construct an adversary~$B$ which attacks the + IND-CCA security of our encryption scheme $\E$. The adversary~$B$ works as follows. + \begin{enumerate} + \item It is given no input, but a pair of oracles $E(\cdot, \cdot)$ and + $D(\cdot)$; the former encrypts either the left or right input, according + to a hidden bit, and the latter decrypts ciphertexts other than those + returned by $E(\cdot, \cdot)$. Its goal is to guess the hidden bit. + \item It sets up a simulation of the game~$\G5$, by running the $\id{init}$ + function, and simulating all of the parties. In particular, it chooses a + random $k \in \Nupto{q_S}$. + \item It sets up accurate simulations of the random oracles $H_K(\cdot)$ + and $H_I(\cdot, \cdot, \cdot, \cdot)$. + \item It runs $A$ in its simulated game. It responds to all of $A$'s + instructions faithfully, except for the matching sessions $S_k$ and + $T_k$. Let $S = S_k = (P_i, P_j, s)$, and $T = T_k = (P_j, P_i, s)$. + \item Suppose $T$ is sent the message $C_S = (\cookie{challenge}, R_S, + c_S)$. Rather than computing $K^* = H_K(r_T R_S)$ and performing the + encryption properly, $B$ queries its left-or-right encryption oracle + $E(\cdot, \cdot)$ on $E(1^{\ell_G}, x_j R_S)$, and sends the resulting + ciphertext~$\chi$ back to~$S$ as part of a message $(\cookie{response}, + R_T, \chi)$. The set $M_T$ is precisely the set of messages constructed + in this fashion. (Recall that challenge messages other than $C_S$ aren't + actually delivered to $T$, since we simulate the responses using the + extractor, as of $\G2$.) + \item Suppose $S$ is sent a message $M = (\cookie{response}, R_T, \chi) \in + M_T$. We immediately stop the simulation, and $B$ returns $0$. + \item Suppose, instead, that $S$ is sent some message $M' = + (\cookie{response}, R, \chi) \notin M_T$. There are two cases to + consider. If $R = R_T$ then we must have $\chi$ distinct from the + ciphertexts returned by the $E(\cdot, \cdot)$ oracle, so we can invoke + the decryption oracle $D(\cdot)$ on $\chi$ to obtain a response $Y$. + Alternatively, if $R \ne R_T$, we can compute the key $K = (K_0, K_1) = + H_K(r_S R)$, and recover $Y = D_{K_0}(\chi)$. In either case, if $Y = + r_S X_j)$ then $S$ would complete at this point: $B$ stops the simulation + and returns $1$. + \item If $A$ exposes $S$ (by corrupting $P_i$ or~$P_j$, or revealing $S$ or + $T$) then we stop the simulation and $B$ returns $0$. + \item Finally, if the game stops, either because $A$ halts, or because of + one of the special rules introduced in earlier games, $B$ returns $0$. + \end{enumerate} + It is clear that $B$'s oracle queries are acceptable, since $|x_j R_S| = + \ell_G$ by definition, and $B$ never queries $D(\cdot)$ on a ciphertext + returned by its encryption oracle. By the rules of~$\G3$, we know that the + game stops immediately if $A$ ever queries $Z_S$, so the key $K^*$ is + independent of everything in $A$'s view except the ciphertexts $\chi$ + output by $S$ and $T$. Therefore, if the hidden bit of the IND-CCA game is + $1$, $B$ accurately simulates $\G5$, whereas if the bit is $0$ then $B$ + accurately simulates $\G6$. We issue no more that $q_M$ encryption or + decryption queries. Finally, $B$'s running time is within the bounds + allowed for $t'$. Therefore, + \[ \Adv{ind-cca}{\E}(B) = \Pr[F_5] - \Pr[F_6] + \le \InSec{ind-cca}(\E; t', q_M, q_M). \] + We construct the adversary~$\bar{B}$ which is the same as $B$ above, except + that $\bar{B}$ returns $0$ whenever $B$ returns~$1$, and \emph{vice versa}. + Clearly + \[ \Adv{ind-cca}{\E}(\bar{B}) + = (1 - \Pr[F_5]) - (1 - \Pr[F_6]) + = \Pr[F_6] - \Pr[F_5] + \le \InSec{ind-cca}(\E; t', q_M, q_M). + \] + This proves the claim. + + Let $\G7$ be the same as $\G6$, except that at the start of the game we + choose a random $m \in \Nupto{n}$, and when the adversary creates the + session $S = S_k = (P_i, P_j, s)$, we abort the game unless $j = m$. + Clearly we have $\Pr[F_6] = n \Pr[F_7]$. + + Finally, we can explicitly bound $F_6$. In $\G6$, the adversary's view is + independent of the correct response $Y_S = r_S X_S = x_j R_S$ to $S$'s + challenge. Therefore, if $A$ manages to send any message $\mu \notin M_T$ + which causes $S$ to complete, then it has impersonated~$P_j$. + \begin{claim} + $\Pr[F_7] \le \InSec{mcdh}(G; t', q_M + q_I)$. + \end{claim} + The present lemma follows from this and the previous claims. + + To prove the claim formally, we construct an adversary~$B'$, which behaves + as follows. + \begin{enumerate} + \item It is given as input a public key $X^*$ and a single challenge $(R^*, + c^*)$, a random oracle $H^*_I(\cdot, \cdot)$, and an oracle $V(\cdot, + \cdot)$, which verifies responses $(R, Y)$. Its goal is to invoke + $V(\cdot, \cdot)$ with a correct response to the challenge. + \item It chooses a random $k \in \Nupto{q_S}$ and $m \in \Nupto{n}$. It + sets up a simulation of the game~$\G7$, by running the $\id{init}$ + function, and simulating all of the parties, except that it gives party + $P_m$ the public key $X^*$. This makes no difference, since $P_m$ + doesn't actually need to give any `honest' responses because of the + change we made in $\G6$. + \item It sets up accurate simulations of the random oracles $H_K(\cdot)$ + and $H_I(\cdot, \cdot, \cdot, \cdot)$, with one exception -- see below. + \item It runs $A$ in its simulated game. It responds to all of $A$'s + instructions faithfully, except for the session $S_k$. Let $S = S_k = + (P_i, P_j, s)$, and let $T = T_k = (P_j, P_i, s)$ be its matching + session. + \item When session~$S$ is created, $B'$ checks that $j = m$, and if not + stops the simulation and halts. Otherwise, $B'$ invokes its oracle~$C()$ + to obtain a pair $(R, c)$. Session~$S$ sends $C_S = (\cookie{challenge}, + R, c)$ as its challenge to~$T$. + \item When $A$ makes a query $H_I(X^*, s, R, Y)$, $B$ answers it by + querying its \emph{own} random oracle $H^*_I(R, Y)$. + \item When $S$ receives a message $(\cookie{response}, R, \chi)$, we + compute $(K_0, K_1) = r_S R$, and $Y = D_{K_0}(\chi)$. If $Y \ne \bot$ + then $B'$ calls $V(R, Y)$. + \item If $A$ reveals $S$ or corrupts $P_i$ or $P_j$ then $B'$ stops the + simulation immediately and halts. + \end{enumerate} + The running time of $B'$ is within the bounds required of $t'$; it makes at + most $q_I$ random-oracle and at most $q_M$ verification queries. Clearly + $B'$ succeeds whenever $F_7$ occurs. The claim follows from + theorem~\ref{thm:wident-sound}. \end{proof} -\subsection{Proof of theorem~\ref{thm:cbc}} -\label{sec:cbc-proof} - -Consider an adversary $A$ attacking CBC encryption using an ideal random -permutation $P(\cdot)$. Pick some point in the attack game when we're just -about to encrypt the $n$th plaintext block. For each $i \in \Nupto{n}$, -let $x_i$ be the $i$th block of plaintext we've processed; let $y_i$ be the -corresponding ciphertext; and let $z_i = P^{-1}(y_i)$, i.e., $z_i = x_i \xor -I$ for the first block of a message, and $z_i = x_i \xor y_{i-1}$ for the -subsequent blocks. - -Say that `something went wrong' if any $z_i = z_j$ for $i \ne j$. This is -indeed a disaster, because it means that $y_i = y_j$ , so he can detect it, -and $x_i \xor y_{i-1} = x_j \xor y_{j-1}$, so he can compute an XOR -difference between two plaintext blocks from the ciphertext and thus -(possibly) reveal whether he's getting his left or right plaintexts -encrypted. The alternative, `everything is fine', is much better. If all -the $z_i$ are distinct, then because $y_i = P(z_i)$, the $y_i$ are all -generated by $P(\cdot)$ on inputs it's never seen before, so they're all -random subject to the requirement that they be distinct. If everything is -fine, then, the adversary has no better way of deciding whether he has a left -oracle or a right oracle than tossing a coin, and his advantage is therefore -zero. Thus, we must bound the probability that something went wrong. - -Assume that, at our point in the game so far, everything is fine. But we're -just about to encrypt $x^* = x_n$. There are two cases: + +\subsection{Proof of theorem~\ref{thm:sk2}} +\label{sec:sk2-proof} + +The proof is almost identical to the proof of theorem~\ref{thm:sk}, in +appendix~\ref{sec:sk-proof}. Unfortunately a black-box reduction doesn't +seem possible. + +We use the games and notation of section~\ref{sec:sk-proof}. + +The change to the check-value calculation doesn't affect key-generation at +all, so the transition to $\G1$ goes through as before. + +The transition from $\G1$ to $\G2$ -- answering challenges using the +extractor -- needs a little care. Let $S = (P_i, P_j, s)$ be a session, and +consider an incoming message $(\cookie{challenge}, R, c)$. \begin{itemize} -\item If $x_n$ is the first block in a new message, we've just invented a new - random IV $I \in \Bin^\ell$ which is unknown to $A$, and $z_n = x_n \xor - I$. Let $y^* = I$. -\item If $x_n$ is \emph{not} the first block, then $z_n = x_n \xor y_{n-1}$, - but the adversary doesn't yet know $y_{n-1}$, except that because $P$ is a - permutation and all the $z_i$ are distinct, $y_{n-1} \ne y_i$ for any $0 - \le i < n - 1$. Let $y^* = y_{n-1}$. +\item If $T = (P_j, P_i, s)$ is the matching session to $S$, and $R = R_T$ is + the public challenge value of $T$, and $c = r_T \xor H_I(R_S, X_j, s, R_T, + r_T X_i)$ is the check-value output by $T$ when it received + $(\cookie{pre-challenge}, R_S)$ as input, then $S$ replies as it did in + $\G1$. +\item If the challenge message is any other message, then we use the + extractor. \end{itemize} -Either way, the adversary's choice of $x^*$ is independent of $y^*$. Let -$z^* = x^* \xor y^*$. We want to know the probability that something goes -wrong at this point, i.e., that $z^* = z_i$ for some $0 \le i < n$. Let's -call this event $C_n$. Note first that, in the first case, there are -$2^\ell$ possible values for $y^*$ and in the second there are $2^\ell - n + -1$ possibilities for $y^*$. Then -\begin{eqnarray}[rl] - \Pr[C_n] - & = \sum_{x \in \Bin^\ell} \Pr[C_n \mid x^* = x] \Pr[x^* = x] \\ - & = \sum_{x \in \Bin^\ell} - \Pr[x^* = x] \sum_{0\le i 2^\ell$ and the theorem is trivially -true, since no adversary can achieve advantage greater than one. - -Let's give the name $W_i$ to the probability that something went wrong after -encrypting $i$ blocks. We therefore want to bound $W_q$ from above. -Armed with the knowledge that $q \le 2^{\ell/2}$, we have -\begin{eqnarray}[rl] - W_q &\le \sum_{0\le i