XOR info
Roberto Fraile Vallejo
Is there any source of information (FAQ, pages, etc) on the web about how to
use One-Time-Pad XOR encryption properly? That is, ways to avoid the problem
of using a pad as long as the plaintext.
For example, I want to encrypt 1024 chunks of 1024 bytes and I only want to
use a short pad, for example, 16 pads of 1024 bytes each. I thought I could
use four bits to identify, on each chunk, the combination of pads being
used, one after the other.
Is possible for an attacker, using known plaintext-ciphertext, to crack the
system? Is there a minimal boundary?
I bet somebody else wrote about this before.
-------------------------------------------------------------------------------
http://www.gui.uva.es/~vallejo Roberto Fraile Vallejo
Bob Bell
On 23 May 1996 09:38:23 GMT, val...@gui.uva.es (Roberto
Fraile Vallejo) wrote:
A one-time-pad is secure only if the length of the pad
exceeds the length of the message. Thus, if you use a
shortened pad, then the result is no longer unbreakable. An
alternative to create a longer "pad" from multiple shorter
pads is to treat the shorter pads as if they are long
"tapes" or sequences of random bytes. If these tapes are of
differing lengths, the resulting string length is the
product of the lengths of the individual tapes. If you are
short of storage area, this might help. However, remember
that for the security of a ont-time-pad, you must use a
given pad value only once.
Principal Engineer
Incite Division, Intecom Inc.
bb...@incite.com
David Wagner
In article <31ab1fec...@stargate.intecom.com>,
Bob Bell <bb...@incite.com> wrote:
> On 23 May 1996 09:38:23 GMT, val...@gui.uva.es (Roberto
> Fraile Vallejo) wrote:
>
> >Is there any source of information (FAQ, pages, etc) on the web about how to
> >use One-Time-Pad XOR encryption properly? That is, ways to avoid the problem
>
> exceeds the length of the message. Thus, if you use a
> shortened pad, then the result is no longer unbreakable. An
> alternative to create a longer "pad" from multiple shorter
> pads is to treat the shorter pads as if they are long
> "tapes" or sequences of random bytes. If these tapes are of
> differing lengths, the resulting string length is the
> product of the lengths of the individual tapes. If you are
> short of storage area, this might help.
Let me repeat the poster's admonition that a one-time pad is only
secure if the length of the pad is (at least) the length of the message.
(Indeed, this is implied in the definition of a one-time pad.)
The poster's second suggestion is a bad one, though. Suppose you take
several shorter pads, repeat each as much as necessary, and xor the
resulting sequences together. It is true that this won't repeat until
about the product (actually, the least common multiple) of the lengths
of the individual tapes in general; but that's misleading. It's also
true that this system is totally insecure once the length of the plaintext
exceeds the sum of the lengths of the tapes.
Mixing shorter tapes is a bad idea. Don't do it.
If you want true provable information-theoretic security, you must use
a one-time pad *with a pad as long as the message*. Of course, this is
far too unwieldy for practical use, so you're better off using DES or
triple DES in one of the standard modes in the real world.
Jerry Leichter
David Wagner wrote:
>
> In article <31ab1fec...@stargate.intecom.com>,
> Bob Bell <bb...@incite.com> wrote:
> > On 23 May 1996 09:38:23 GMT, val...@gui.uva.es (Roberto
> > Fraile Vallejo) wrote:
> >
> > >Is there any source of information (FAQ, pages, etc) on the web about how to
> > >use One-Time-Pad XOR encryption properly? That is, ways to avoid the problem
> >
> > A one-time-pad is secure only if the length of the pad
> > and XOR them.]
>
> Let me repeat the poster's admonition that a one-time pad is only
> secure if the length of the pad is (at least) the length of the message.
> (Indeed, this is implied in the definition of a one-time pad.)
>
>
> Mixing shorter tapes is a bad idea. Don't do it.
>
> If you want true provable information-theoretic security, you must use
Both messages repeat a common oversimplification, which can be dangerous.
The issue is *not* the length of the one-time pad. The issue is the equivocation
added.
Suppose I generate a one-time pad of random *bytes*, but only vary the bottom bit
of the bytes. Even if I generate a pad as long as a stream of English text,
you'll have no trouble reading the text, even just "by eye". Why? Because there
is a great deal of redundancy in English text. The usual estimate is that each
succes- sive letter you receive carries a bit more than 2 bits of information -
i.e., if you were allowed a few more than 4 guesses, you'd almost always be able
to get the next letter, given the preceding ones. In information theory, the
measure of your uncertainty about the next letter is your equivocation. For a
one-time pad to be absolutely secure in the information-theoretical sense, it
must increase your equivocation to the point where you know no more about the
message than you would have having seen none of it. (If you know the message is
English text, you always know that "e" is much more likely than "q".) If you've
somehow seen some of the message encrypted under a one-time pad, to guess the
next letter, you are really guessing two things: The next letter, and the
one-time-pad value it was XOR'ed with. The total number of combinations of those
two things must be large enough that you get no useful information.
The one-time-pad value is chosen independently of the next letter, and in a
proper one-time-pad system, it's chosen uniformally at random from some
distribution. That makes it easy to calculate exactly how much equivocation it's
adding. If you added 3 bits of equivocation to the 2 bits or so that English
leaves you with, any letter would be equally likely, and the system would be
safe. (But just XOR'ing the bottom 3 bits of a letter in ASCII probably leaks
some additional information because of the way the alphabet is structured and how
it appears in ASCII.)
This analysis shows you why things like book codes - using text from a book as
the one-time-pad - are not secure. The problem is that there is that the book is
*not* a source of random letters; it obeys the English distribution, so is only
adding a few bits of equivocation. In fact, about 2 bits - not nearly enough.
On the other hand, using, say, 3 books and XOR'ing all the values together to
form the one-time pad probably *does* add enough equivocation. But you can never
repeat the text used! If you do, the attacker is no longer dealing with text
drawn from all possible English books; he is dealing with text drawn from the
same book as was used in previous messages. This is a *much* smaller space, so
the equivocation added is much smaller, too. That's why repetition is deadly to
a one-time pad. Even if the one-time pad is really randomly chosen, and is only
used *twice*, given enough effort, the code can be broken. (That's exactly what
the Western cryptographers did in the Venona decrypts.)
In summary: Don't think "lengths"; think "uncertainty". In any one-time pad
system, solving for the cleartext and solving for the pad are exactly equivalent
problems. Since you can't make the *text* harder to guess, you have to make the
*pad* hard enough to guess that you make up for anything the attacker may know
about the text.
-- Jerry
Chris Trobridge
> That is, ways to avoid the problem of using a pad as long as the
> plaintext.
The moment you start reusing the pad it ceases to be a one-time pad.
> I bet somebody else wrote about this before.
Yep. A few weeks back someone wanted to do something similar (using 2
1-time pads of different lengths). It was suggested that this posed
little extra difficulty to cryptanalysis, and my gut feeling is that your
scheme will fall the same way.
Sorry for the lack of 'solid' analysis!
It was also suggested that this should be included in the FAQ!
Chris
Rick F. Hoselton
bb...@incite.com (Bob Bell) wrote:
>A one-time-pad is secure only if the length of the pad
>exceeds the length of the message. Thus, if you use a
>shortened pad, then the result is no longer unbreakable.
I agree.
>An
>alternative to create a longer "pad" from multiple shorter
>pads is to treat the shorter pads as if they are long
>"tapes" or sequences of random bytes. If these tapes are of
>differing lengths, the resulting string length is the
>product of the lengths of the individual tapes.
If the lengths are relatively prime to each other, then the combined
key will have an apparent length equal to the product of the individual
key lengths.
However, the system can be solved with known plaintex equal to the
SUM of the individual lengths plus one character, minus the number of
pads being combined. It actually requires less plaintext than it would
if you just concatenated all the pads.
If we use "+" for XOR, the cipher looks like:
Ciphertext(n) =Plaintext(n) + Sum ( Pad_i (n mod len(Pad_i) )
So if we have x bytes of known plaintext and ciphertext, we can setup
x equations in the above format. If the bytes are contiguous, the
equations are independent. If there are at least as many equations as
unknowns, we can use Gaussian elimination to find each character of
each pad. Since only the sum of the pad characters matters, there are
actually many solutions that work equally well. We can assume that
some of the pad characters are zero, and solve for the other pad characters
that make the known plaintext work.
diegoher...@gmail.com
Confío en que te llegue un mail, aún siendo este post del 96 😅
Soy Diego Hermosilla, de Valladolid, ando tiempo tratando de contactar contigo, solo para retomar una antigua amistad, si fuiste al colegio el pilar, y solias jugar videojuegos conmigo, trata de contactarme, please.
Un saludo