Re: [Cfrg] Repeated one-time pad

Marshall Eubanks <marshall.eubanks@gmail.com> Thu, 14 July 2011 21:44 UTC

Return-Path: <marshall.eubanks@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id BA26021F8B03 for <cfrg@ietfa.amsl.com>; Thu, 14 Jul 2011 14:44:51 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -103.201
X-Spam-Level:
X-Spam-Status: No, score=-103.201 tagged_above=-999 required=5 tests=[AWL=0.131, BAYES_00=-2.599, GB_I_LETTER=-2, HTML_MESSAGE=0.001, J_CHICKENPOX_33=0.6, RCVD_IN_DNSWL_LOW=-1, SARE_HTML_USL_OBFU=1.666, USER_IN_WHITELIST=-100]
Received: from mail.ietf.org ([64.170.98.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id beI-v-2QCUTE for <cfrg@ietfa.amsl.com>; Thu, 14 Jul 2011 14:44:47 -0700 (PDT)
Received: from mail-yx0-f182.google.com (mail-yx0-f182.google.com [209.85.213.182]) by ietfa.amsl.com (Postfix) with ESMTP id EF0B821F8B00 for <cfrg@irtf.org>; Thu, 14 Jul 2011 14:44:46 -0700 (PDT)
Received: by yxl31 with SMTP id 31so369937yxl.13 for <cfrg@irtf.org>; Thu, 14 Jul 2011 14:44:46 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=Tff49MS5Gr3iLYwTKk0T7P92stCgz1D/7AqMUkFlbgQ=; b=BTdGBA61s3oyg1V1su3qLueAHGKDFSnHsJnqCBLQ1ZJX7xkrWkCpTcL6S2OvHLpdMY XOlHOHsFO0VKup54wlV1Dlle3U3lTqaxDqLXHapAH686g1bNL8EBjSi/pitTfWoStEKi s2bc7nS3LA82sJe9DOWE1o5FiIXilIfKoY5/4=
MIME-Version: 1.0
Received: by 10.236.156.68 with SMTP id l44mr162975yhk.142.1310679886327; Thu, 14 Jul 2011 14:44:46 -0700 (PDT)
Received: by 10.147.98.1 with HTTP; Thu, 14 Jul 2011 14:44:46 -0700 (PDT)
In-Reply-To: <4E1F467C.8090702@gmail.com>
References: <mailman.117.1310670016.1187.cfrg@irtf.org> <4E1F467C.8090702@gmail.com>
Date: Thu, 14 Jul 2011 17:44:46 -0400
Message-ID: <CAJNg7VKsTgJXp2JhcXEmuom=V9qTytz2wx3hcgJdzb743z3dmw@mail.gmail.com>
From: Marshall Eubanks <marshall.eubanks@gmail.com>
To: Yaron Sheffer <yaronf.ietf@gmail.com>
Content-Type: multipart/alternative; boundary=20cf303f680e09ee2304a80e71b0
Cc: cfrg@irtf.org
Subject: Re: [Cfrg] Repeated one-time pad
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Thu, 14 Jul 2011 21:44:51 -0000

On Thu, Jul 14, 2011 at 3:41 PM, Yaron Sheffer <yaronf.ietf@gmail.com>wrote;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<http://en.wikipedia.org/wiki/One-time_pad#True_randomness>)s>).
> 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 <
> simon@josefsson.org> To: Ted Krovetz <ted@krovetz.net> Cc: cfrg@irtf.orgSubject: Re: [Cfrg] Request For Comments: OCB Internet-Draft Message-ID: <
> 87ipr5gukz.fsf@latte.**josefsson.org <87ipr5gukz.fsf@latte.josefsson.org>>
> Content-Type: text/plain Ted Krovetz <ted@krovetz.net> writes:
>
>> I have just submitted an internet-draft for OCB to the IETF.
>>>
>>>   http://datatracker.ietf.org/**doc/draft-krovetz-ocb<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).
>>
>>
> ______________________________**_________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/**listinfo/cfrg<http://www.irtf.org/mailman/listinfo/cfrg>
>