Subject: [Cfrg] Repeated one-time pad

From: Yaron Sheffer <[email-masked]>
Date: Thu, 14 Jul 2011 22:41:48 +0300

Regarding "immediate key disclosure": is is well known that reuse of a 
stream cipher or a one-time pad with different plaintexts leads to 
immediate exposure of the plaintext (see e.g. 
http://en.wikipedia.org/wiki/One-time_pad#True_randomness). For a course 
I am teaching, I would appreciate pointers to the algorithms that are 
used for this cryptanalysis and/or source code that implements this attack.

Thanks,
     Yaron

Message: 2 Date: Thu, 14 Jul 2011 10:00:44 +0200 From: Simon Josefsson 
<[email-masked]> To: Ted Krovetz <[email-masked]> Cc: 
[email-masked] Subject: Re: [Cfrg] Request For Comments: OCB 
Internet-Draft Message-ID: <[email-masked]> 
Content-Type: text/plain Ted Krovetz <[email-masked]> writes:
>> I have just submitted an internet-draft for OCB to the IETF.
>>
>>    http://datatracker.ietf.org/doc/draft-krovetz-ocb
>>
>> I'd appreciate any comments you may have on how to make the draft better.
> It would help if you explained (in the security considerations) what
> happens if a nonce is repeated.  The question of failure modes of
> authenticated encryption modes has come up in several different
> contexts.  It turns out that different AEAD modes have different failure
> properties.
>
> In particular, you want to address whether repeat of a nonce leads to
> immediate key disclosure, or whether the key can be found after some
> computation faster than obvious attacks, or whether it can only lead to
> recovery of the plaintext, and/or whether it depends on the plaintext as
> well (e.g., something interesting happens if the plaintexts are related).
>

---

From: "Paterson, Kenny" <[email-masked]>
Date: Thu, 14 Jul 2011 20:45:03 +0000

Hi Yaron,

The paper you want is by Mason et al. from CCS a few years back:

@inproceedings{DBLP<http://dblp.uni-trier.de/db/about/bibtex.html>:conf/ccs/MasonWES06,

  author    = {Joshua Mason and
               Kathryn Watkins and
               Jason Eisner and
               Adam Stubblefield},
  title     = {A natural language approach to automated cryptanalysis of
               two-time pads},
  booktitle = {ACM Conference on Computer and Communications Security},
  year      = {2006},
  pages     = {235-244},
  ee        = {http://doi.acm.org/10.1145/1180405.1180435},
  crossref  = {DBLP:conf/ccs/2006usa},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

I had a masters student re-implement the algorithms in this paper last summer - they performed very well, but not quite as well as the authors indicated in their paper.

Cheers

Kenny

On 14 Jul 2011, at 20:41, Yaron Sheffer wrote:

Regarding "immediate key disclosure": is is well known that reuse of a stream cipher or a one-time pad with different plaintexts leads to immediate exposure of the plaintext (see e.g. http://en.wikipedia.org/wiki/One-time_pad#True_randomness). For a course I am teaching, I would appreciate pointers to the algorithms that are used for this cryptanalysis and/or source code that implements this attack.

Thanks,
   Yaron

Message: 2 Date: Thu, 14 Jul 2011 10:00:44 +0200 From: Simon Josefsson <[email-masked]<mailto:[email-masked]>> To: Ted Krovetz <[email-masked]<mailto:[email-masked]>> Cc: [email-masked]<mailto:[email-masked]> Subject: Re: [Cfrg] Request For Comments: OCB Internet-Draft Message-ID: <[email-masked]<mailto:[email-masked]>> Content-Type: text/plain Ted Krovetz <[email-masked]<mailto:[email-masked]>> writes:
I have just submitted an internet-draft for OCB to the IETF.

_______________________________________________
Cfrg mailing list
[email-masked]<mailto:[email-masked]>
http://www.irtf.org/mailman/listinfo/cfrg

---

From: Marshall Eubanks <[email-masked]>
Date: Thu, 14 Jul 2011 17:44:46 -0400

On Thu, Jul 14, 2011 at 3:41 PM, Yaron Sheffer <[email-masked]>wrote:

> stream cipher or a one-time pad with different plaintexts leads to immediate
> exposure of the plaintext (see e.g. http://en.wikipedia.org/wiki/**
> One-time_pad#True_randomness<http://en.wikipedia.org/wiki/One-time_pad#True_randomness>).
> For a course I am teaching, I would appreciate pointers to the algorithms
> that are used for this cryptanalysis and/or source code that implements this
> attack.
>
> The attack is pretty simple and can be done by hand.

If (as was common in the spy world) the one time pad was just XORed (or
summed) with the plain text, XOR'ing two of cipher-texts with the same
 "one-time" pad in the same phase yields an XOR  of the two underlying
plain-texts, which lends itself to plaintext cribs and a "crab-like"
attack (i.e., if you can guess one word in one plain-text, it will, when
XORed with the XOR of the two cipher-texts, reveal part of the other
plain-text, which, when extended, then will  reveal more of the first
plain-text, and so on until both are decrypted. Even if the phase of the OTP
isn't known (e.g., if there is filler text at the beginning), it should be
easy to determine it using the index of coincidence (which should peak when
the OTPs are aligned in phase).

This is (from my understanding) how the Venona break was done.

Sounds like a reasonable pen and paper exercise for your students for me.

Now, what I have is always wondered is whether the non-randomness of the
Russian OTPs used in their spy work was  enough to have a break without
reuse of the OTPs. (These were prepared by typists instructed to type
randomly, and so weren't entirely random, for example letters were almost
never doubled and a left hand letter was generally followed by a right hand
letter. Not a lot of non-randomness, but a little can go a long way...)

Regards
Marshall

> Thanks,
>    Yaron
>
> Message: 2 Date: Thu, 14 Jul 2011 10:00:44 +0200 From: Simon Josefsson <
> [email-masked]> To: Ted Krovetz <[email-masked]> Cc: [email-masked]: Re: [Cfrg] Request For Comments: OCB Internet-Draft Message-ID: <
> 87ipr5gukz.fsf@latte.**josefsson.org <[email-masked]>>
>>>   http://datatracker.ietf.org/**doc/draft-krovetz-ocb<http://datatracker.ietf.org/doc/draft-krovetz-ocb>
>>>
> ______________________________**_________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/**listinfo/cfrg<http://www.irtf.org/mailman/listinfo/cfrg>
>