Cryptography-Digest Digest #690, Volume #13 Thu, 15 Feb 01 05:13:01 EST
Contents:
Re: National Security Nightmare? (John Savard)
Re: National Security Nightmare? (JPeschel)
Re: National Security Nightmare? ("Paul Pires")
Re: National Security Nightmare? (JPeschel)
Re: National Security Nightmare? (JPeschel)
Indicative key generation, encryption/decryption time ("Adrian Wee")
Re: /dev/random under Linux (Pascal Junod)
Re: Building PGP 658 under Linux. ("Benjamin Scherrey")
speed vs security ("-")
Re: speed vs security (Paul Rubin)
Re: What is an Inorder Algorithm? (Virgil)
Re: speed vs security ("-")
Re: Super strong crypto (wtshaw)
A Chosen-Plaintext Attack on a simple Dynamic Transposition Cipher ("John A.
Malley")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: National Security Nightmare?
Date: Thu, 15 Feb 2001 05:05:12 GMT
On 15 Feb 2001 04:38:40 GMT, [EMAIL PROTECTED] (JPeschel)
wrote, in part:
>I haven't seen the IEEE article. But if law enforcement in LA
>county is building a networked cracker with 16 servers
>they are probably talking about cracking DES, or 40- and
>56-bit RC4, by exhaustive search of the key space.
Possibly, also, they hope to crack things enciphered with poorly
chosen pass phrases, even if the pass phrase is ultimately used as
input to a secure algorithm with a large key.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Date: 15 Feb 2001 06:04:55 GMT
Subject: Re: National Security Nightmare?
[EMAIL PROTECTED] (John Savard) writes:
>On 15 Feb 2001 04:38:40 GMT, [EMAIL PROTECTED] (JPeschel)
>wrote, in part:
>
>>I haven't seen the IEEE article. But if law enforcement in LA
>>county is building a networked cracker with 16 servers
>>they are probably talking about cracking DES, or 40- and
>>56-bit RC4, by exhaustive search of the key space.
>
>Possibly, also, they hope to crack things enciphered with poorly
>chosen pass phrases, even if the pass phrase is ultimately used as
>input to a secure algorithm with a large key.
Eh, could be.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: National Security Nightmare?
Date: Wed, 14 Feb 2001 22:30:54 -0800
John Savard <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> On 15 Feb 2001 04:38:40 GMT, [EMAIL PROTECTED] (JPeschel)
> wrote, in part:
>
> >I haven't seen the IEEE article. But if law enforcement in LA
> >county is building a networked cracker with 16 servers
> >they are probably talking about cracking DES, or 40- and
> >56-bit RC4, by exhaustive search of the key space.
>
> Possibly, also, they hope to crack things enciphered with poorly
> chosen pass phrases, even if the pass phrase is ultimately used as
> input to a secure algorithm with a large key.
This sounds much more likely to me. Considering the prevalence of password
protections and the difficulty in picking a "good" one, they would probably have
much success. Sounds like they are going after Quickbooks and excell, not PGP.
Paul
>
> John Savard
> http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Date: 15 Feb 2001 06:44:23 GMT
Subject: Re: National Security Nightmare?
Paul Pires [EMAIL PROTECTED] writes:
>John Savard <[EMAIL PROTECTED]> wrote in message
>news:[EMAIL PROTECTED]...
>> On 15 Feb 2001 04:38:40 GMT, [EMAIL PROTECTED] (JPeschel)
>> wrote, in part:
>>
>> >I haven't seen the IEEE article. But if law enforcement in LA
>> >county is building a networked cracker with 16 servers
>> >they are probably talking about cracking DES, or 40- and
>> >56-bit RC4, by exhaustive search of the key space.
>>
>> Possibly, also, they hope to crack things enciphered with poorly
>> chosen pass phrases, even if the pass phrase is ultimately used as
>> input to a secure algorithm with a large key.
>
>This sounds much more likely to me. Considering the prevalence of password
>protections and the difficulty in picking a "good" one, they would probably
>have
>much success. Sounds like they are going after Quickbooks and excell, not
>PGP.
>
Nah, that's too much money and power to waste on cracking Quickbooks
and Excel. Law Enforcement can hire Kuslich, Thompson, or others
to do that!
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Date: 15 Feb 2001 06:54:18 GMT
Subject: Re: National Security Nightmare?
[EMAIL PROTECTED] that would be me (JPeschel) wrote:
>Nah, that's too much money and power to waste on cracking Quickbooks
>and Excel. Law Enforcement can hire Kuslich, Thompson, or others
>to do that!
And now that I think about it some more: they could hire me; I could
use a trip to somewhere without snow and with temperatures above
-20 F.
J
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: "Adrian Wee" <[EMAIL PROTECTED]>
Subject: Indicative key generation, encryption/decryption time
Date: Thu, 15 Feb 2001 15:08:40 +0800
Hello there,
I am working on a project that requires encryption and I would like to
get some indicative time (say for 1 milllion process per second) for key
generation and encryption/decryption time for some popular algorithm like
DES, RSA and so on as my system is processing power limited.
Also, where can I find the codes in C/C++ for popular algorithms?
Thanks
Adrian
------------------------------
Date: Thu, 15 Feb 2001 08:21:37 +0100
From: Pascal Junod <[EMAIL PROTECTED]>
Subject: Re: /dev/random under Linux
On Wed, 14 Feb 2001, JCA wrote:
> I am trying to collect sufficient amounts of such data myself
> so that I can subject it to the Diehard tests, but I am getting
> sick and tired of having to move the mouse or typing rubbish
> in order to keep the entropy pool reasonably active.
The following should be sufficient in order to save some hours of
moving the mouse (to run as root):
#! /usr/bin/perl
while (1) {
`cat /dev/sda5 > /dev/null`;
}
where /dev/sda5 (replace it by one of your partitions) is a big disk
partition. This produces a lot of disk interrupts whose intertimings
are processed by the entropy pool.
By th way, if diehard complains, then you have a nice result on SHA,
because the output is hashed by this function.
A+
Pascal
--
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
* Pascal Junod, [EMAIL PROTECTED] *
* Laboratoire de S�curit� et de Cryptographie (LASEC) *
* INF 240, EPFL, CH-1015 Lausanne, Switzerland ++41 (0)21 693 76 17 *
* Place de la Gare 12, CH-1020 Renens ++41 (0)79 617 28 57 *
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
------------------------------
From: "Benjamin Scherrey" <[EMAIL PROTECTED]>
Subject: Re: Building PGP 658 under Linux.
Date: Thu, 15 Feb 2001 01:36:54 -0500
Ian,
Thanx very much for the patches. I would have given up long before
generating such code for myself. However, I'm patch impaired and always
have difficulty getting such things back in (I always d/l the full kernel
for example). Could you please post some instructions on how to apply the
patch (including where I should be to apply it, I always get my directory
position wrong it seems)? To copy the patch out of the news posting, what
exactly begins/ends the patch so I know what to cut out?
Thanx again & later,
Ben Scherrey
In article <96dj4p$i5h$[EMAIL PROTECTED]>, "Ian Goldberg"
<[EMAIL PROTECTED]> wrote:
> So I've spent quite a while tracking down why the source code for PGP
> 6.58 under Linux (Redhat 6.2):
>
> a) doesn't compile, and b) when I get it to compile, produces encrypted
> messages that the
> standard binary can't read
>
> Len Sassaman and I finally got it working. Here's a patch to make PGP
> 6.58 both compile *and work* under Redhat 6.2:
<patches snipped>
------------------------------
From: "-" <[EMAIL PROTECTED]>
Subject: speed vs security
Date: Thu, 15 Feb 2001 07:32:30 -0000
Hi
does anyone know of any books or sites that compare the different speeds and
performance of various encryption algorithms? I'm writing an app for Palm
OS, and I've implemented the blow fish 2 algorithm but it's just *way* too
slow.
I'd appreciate any pointers.
dylan
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: speed vs security
Date: 14 Feb 2001 23:55:20 -0800
"-" <[EMAIL PROTECTED]> writes:
> does anyone know of any books or sites that compare the different speeds and
> performance of various encryption algorithms? I'm writing an app for Palm
> OS, and I've implemented the blow fish 2 algorithm but it's just *way* too
> slow.
FIrst of all, what the heck is Blowfish 2? Do you mean Twofish?
That's an entirely different algorithm from Blowfish.
Second, both of these algorithms are very fast for block ciphers.
The RC4 stream cipher is probably the simplest thing that's faster.
You should be able to get reasonable security from Blowfish with only 8
rounds, so you can double its speed that way, at some cost in security.
But if Blowfish and Twofish aren't fast enough for your application,
maybe you need to tune your implementation. What are you trying to do?
------------------------------
From: Virgil <[EMAIL PROTECTED]>
Crossposted-To:
comp.lang.c,alt.comp.lang.learn.c-c++,sci.math,comp.lang.c++,comp.lang.java.programmer,comp.programming
Subject: Re: What is an Inorder Algorithm?
Date: Thu, 15 Feb 2001 01:59:40 -0700
In article <[EMAIL PROTECTED]>, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
> Sorry, it seems to be a result of Knuth's mistake. In
> his first edition (1968), on p.316 about traversing binary
> trees, there stood the following text:
>
> Postorder traversal
> Traverse the left subtree
> Visit the root
> Traverse the right tree
>
> He gave also an example that conformed to that.
>
> M. K. Shen
Even Homer nods.
------------------------------
From: "-" <[EMAIL PROTECTED]>
Subject: Re: speed vs security
Date: Thu, 15 Feb 2001 08:53:09 -0000
Hi paul
sorry, i meant blowfish, don't knowhow the '2' got there :)
I'm writingan app, and for x reason, the text needs to be stored in
encrypted form. W're talking 200K of text maximum, but there's a good 15
second wait if I try to encrypt/decrypt that much text.
I'll try your suggestion, failing that, I'll post the code.
thanks
Paul Rubin <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> "-" <[EMAIL PROTECTED]> writes:
> > does anyone know of any books or sites that compare the different speeds
and
> > performance of various encryption algorithms? I'm writing an app for
Palm
> > OS, and I've implemented the blow fish 2 algorithm but it's just *way*
too
> > slow.
>
> FIrst of all, what the heck is Blowfish 2? Do you mean Twofish?
> That's an entirely different algorithm from Blowfish.
>
> Second, both of these algorithms are very fast for block ciphers.
> The RC4 stream cipher is probably the simplest thing that's faster.
>
> You should be able to get reasonable security from Blowfish with only 8
> rounds, so you can double its speed that way, at some cost in security.
>
> But if Blowfish and Twofish aren't fast enough for your application,
> maybe you need to tune your implementation. What are you trying to do?
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Super strong crypto
Date: Thu, 15 Feb 2001 02:44:44 -0600
In article <[EMAIL PROTECTED]>, "Douglas A. Gwyn"
<[EMAIL PROTECTED]> wrote:
> wtshaw wrote:
> > But, unfortunately, most did not understand the crux of getting real
> > security. When DES was announced many years ago, I doubled over laughing
> > at it. I knew the score then. It is still much of a joke that real
> > security was and is sidestepped.
>
> If you really have insights into "real security", please write them
> up in a form that others can understand and publish them. DES met
> its design goals admirably, and in fact exceeded them. Even today
> nobody admits to knowing any attack on the DEA that is appreciably
> better than a brute force search of the key space. That is quite
> an accomplishment for a cryptosystem that has been the subject of
> intense scrutiny by so many for so long.
Considering what was in the public eye at the time, it was the best thing
going, but I was after bigger game long before that, and I was on the
right track. Too many people forget Shannon, that the amount of
ciphertext necessary for breaking a cipher is a critical part of strength.
What has been traded is a substantial requirement for demanding much
volume to break a cipher. In the poke in return is computational
complexity in small static groups. And, has it been pointed out so well
here, such cipher systems are incapable of masking trends in highly
redundant plaintexts such as graphics and data bases.
Obviously, lots of old ciphers are inadequate in complexity, making brute
force a viable means of attack, but the standards of good cryptographic
design still arise in from the classics, and they are not to be ignored if
you know what's good for you.
As my comprehensive research into redundancy clearly shows, binary
management is about the worst of choices for intensive data churning.
Indeed, the idea that keys should be worked to death, courtesy of some
bright boy at NSA, is miserable advice.
What I know is that better security, even more simple in concept, is
practical. I can effectively solve such masking problems in variable
sized blocks mentioned above and at just about any DC to light arbitrary
security level, in an easily explained generic form. It's fun to take
someone who knows neither higher mathematics, nor anything about
computers, explain a cryptosystem, and see them successfully work the
algorithm on their own as a test. Try that with DES, or whaterver turns
you on.
Surely DES was machined like a Swiss watch, paid for by pilfered gold, but
as far as yield for complexity, it is too intensive. So, we have lots of
people that did not stray from its rough pattern of what they see as
success, and I understand why it is difficult to go too far from the
beach.
Talking of real security, I guess that few people have build custom
modems, digital interfaces, fail safe features for absolute confirmation
of two-way communications, all from scratch, but I have, and on a
commercial scale, turn-key, no one to blame for failure or credit for
success but myself. I did lots of redesign to make inherited equipment
work, and designed my share of successes, and failures in the process of
learning. I know that a sound set of reasonable objectives for highly
secure systems can be done, not what we have in the internet today, nor in
most computers.
People simply fail to grasp what a respectable sized minority of us know
about security from experience, even take for granted. For some of us,
there are no big threats, yet for most, no real security. Boy, it's a
real shame, like I heard on TV last night, that so many feel like a
solving security problems we have today is impossible. How stupid can
people get, to try to politic themselves out of a nightmare of their own
creation, as bad design philosophy continually tears at the very heart of
basic security.
It's such a hollow sound to cry that oppressive measures must be taken to
protect us from such and such, for fear of real security in the hands of
people at large. In our case of general security, or lack of it, wanting
to control from on high has so often corrupted the spread of good
technology. How can I make that plainer? Well, political power mongers
fear that they are not all powerful. Surprise, they aren't. If there is
something they cannot control, they foster a poor replacement, or ban the
are on pretense. The problem is that inferior technology reaches out to
sting everybody. Dig up the worst conjecture you can find to whip the
public into being true believers. And, if you have insufficient enemies
to get your way, make enough people mad and you will have enemies to
thrash.
Picture some thinking the US is an island, or that government is a
repository of good sense and wise action. There is something too powerful
about free and good ideas to completely suppress them, and the ability for
people to find them is a universal human commodity, and I speak to push
the positive nature of some fundamental and useful ideas.
Be glad that I edited out lots of paragraphs from the above...
--
Better to pardon hundreds of guilty people than execute one
that is innocent.
------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: A Chosen-Plaintext Attack on a simple Dynamic Transposition Cipher
Date: Thu, 15 Feb 2001 01:42:28 -0800
SUMMARY
It is with some excitement (and slight trepidation :-) ) I present a
chosen plaintext attack on a simple Dynamic Transposition cipher to
determine the sequence of permutations used to encipher the chosen
plaintext. The same key (sequence of permutations) is applied to each
plaintext.
The attack requires only N/2 + 1 chosen plaintexts for a N bit,
bit-balanced block DT cipher as defined below.
I use a Dynamic Transposition cipher meeting the two basic requirements
for such a cipher as previously posted in the group:
(1) collecting plaintext data in N bit, bit-balanced blocks.
(2) permutating the bits in each blocks such that the permutation
applied to the block is uniformly selected at random from the set of all
possible permutations of N bits.
This is the first attack of this kind I've done on my own. This post
presents some (hopefully) interesting results in attempts to better
understand the strengths of Dynamic Transposition ciphers. Critique and
comments are most welcome, and I do hope I did not make any fundamental
errors.
THE SIMPLE DYNAMIC TRANSPOSITION CIPHER MODEL
Let the binary message M be divided up into blocks M(n), n = 1 to k, of
b bit length.
M(n) is a b bit long binary string.
Let ~M(n) represent the ones complement of the binary string M(n). ~M(n)
is also b bits long.
Let P(n) be the concatenation of M(n) and ~M(n) such that P(n) = M(n) |
~M(n) and | means "concatenate the binary strings." P(n) is a 2b bit
long binary string.
Let N = 2b where N is the integer number of bits in P(n).
P(n) is a N bit bit-balanced plaintext block. The entire plaintext P for
the message M is the concatenated string of blocks P(n) for n = 1 to k.
Let PI_n( ) be a permutation of an N bit binary string chosen uniformly
at random from the set of possible permutations of N bits. There are N!
possible permutations to choose from.
The probability that PI_n( ) equals any particular permutation is 1 /
N! Each possible permutation is equally likely for each block of
plaintext to encipher.
Let C(n) be the N bit binary string resulting from the application of
PI_n( ) to the nth plaintext block P(n). Then C(n) = PI_n( P(n) ).
C(n) is a N bit bit-balanced ciphertext block. The entire ciphertext C
for the plaintext P is the concatenated string of blocks C(n) for n = 1
to k.
Given P(n) is bit-balanced (#0 = #1), there are N! /((N/2)! (N/2)!)
permutation values for PI_n() that take a given P(n) plaintext string to
the same C(n) ciphertext string.
The sequence of permutations applied to plaintext blocks, PI_n() for n =
1 to k, is the Dynamic Transposition cipher key. This key is secret and
known only to Alice and Bob.
Alice can encipher a message M by converting it block by block to
bit-balanced plaintext and then permutating each block into ciphertext.
Bob can decrypt the ciphertext by applying the inverse permutation for
PI_n() to each block to reveal the bit-balanced plaintext blocks. Bob
recovers the original message blocks M(n) from the left half of each
block P(n) to reconstruct the original message M from Alice.
THE PROBLEM
Eve cannot determine the exact permutation applied to the nth block of
plaintext when given P(n) and C(n).
Suppose Eve can get as many plaintext blocks P_i(n) as she wants, all
encrypted with the SAME permutation PI_(n).
How many blocks of plaintext enciphered with the same permutation PI_n()
does Eve need to determine the value of PI_n() used?
This is a chosen-plaintext attack on a simple DTC with a fixed key. Eve
gets to select the plaintext block values to be enciphered with a secret
key (permutations) and she gets the resulting ciphertext.
THE SOLUTION
Eve knows it is not possible to pin-point the exact permutation used to
transform a known P(n) into a known C(n) since there are so many
different PI_n() permutation values that take a given P(n) plaintext
string to the same C(n) ciphertext string. If only P(n) was NOT
bit-balanced - then C(n) wouldn't be, either, and it would be ever so
much easier to figure out which bit positions swap with which bit
positions in the N-bit string (block).
Imagine a plaintext block with just a single 1 value and N-1 0 values.
When enciphered with PI_n() that single 1 value would swap places with a
0 value and uniquely indicate the effects of the permutation on that
single bit location in the N bit string. For example, Eve has a N-bit
plaintext string with a 1 in the leftmost position the N-1 other
positions filled with 0 bits, like
10000....000
It's encrypted with the unknown permutation PI_n() and generates the
output ciphertext block
00001...000.
She knows the 1st bit location swaps places with the jth bit position.
And she also knows the jth bit position swaps places with the 1st bit
position.
If she shifts the 1-bit in the plaintext block to the next bit position
as
01000...000,
and gets it enciphered with the unknown permutation, she'd know the
location in the N bit string that swaps content with the 2nd bit
position, like
0000...001,
for example.
In this manner Eve could "walk" a single 1 bit value from the leftmost
bit in the plaintext (call it the first bit) to the N-1st bit,
enciphering each plaintext to produce ciphertext strings with each
ciphertext string having only a single 1 bit value. The 1 bit's location
in the ciphertext compared to the 1 bit's position in the plaintext
allows Eve to step-by-step reconstruct the unique permutation actually
used out of the N! possible permutations.
But how can Eve do this with N bit bit-balanced blocks? She can't apply
single 1-bit value strings when using DTC.
She relies instead on the following fact:
PI( A * B ) = PI( A ) * PI ( B ),
where A and B are binary strings of equal length, * is a bit-wise
logical operator acting on strings and PI() is a permutation of a binary
string.
Every plaintext block P(n) = M(n) | ~M(n) can be decomposed into two
strings that generate P(n) when bit-wise logically operated recombined.
Example:
P(n) can be decomposed into P_l(n) = M(n) | OOO...O and P_r(n) =
000...0 | ~M(n)
P_l(n) is a string of N/2 0 bits concatenated with the string of bits
M(n). P_r(n) is the string of bits ~M(n) concatenated onto a string of
N/2 0 bits.
P(n) = P_l(n) XOR P_r(n).
=======================
Eve figures out how to get the ciphertext that results from "walking a
1" through the plaintext N bit block by combining the ciphertext outputs
of particular patterns of bit-balanced plaintext.
Eve "walks a 1" through the N/2 bit length string M(n) and gets the
resulting corresponding bit-balanced plaintext block P(n) enciphered by
the same permutation PI_n(), as follows:
Let M_i(n) be a string of N/2 bits, 1 <= i <= N/2, where the ith bit is
a 1 and all other bits are 0s. Then ~M_i(n) is a string of N/2 bits, 1
<= i <= N/2, where the ith bit is a 0 and all other bits are 1s. The
resulting N bit bit balanced plaintext is P_i(n) = M_i(n) | ~M_i(n).
So for example, Eve constructs
P_1(n) = 1000...00 | 0111...11
P_2(n) = 0100...00 | 1011...11
P_3(n) = 0010...00 | 1101...11
.
.
.
P_N/2(n) = 0000...01 | 1111...10
Eve gets each P_i(n) enciphered by the same permutation PI_n() and gets
back
C_i(n) = PI_n( P_i(n) ), for i = 1 to N/2.
These C_i(n) are all bit balanced.
Eve needs one more special value enciphered with the unknown permutation
to proceed with the attack.
Let M_0(n) be a string of N/2 bits where all bits are 0s. Then ~M_i(n)
is a string of N/2 bits where all bits are 1s. The resulting N bit bit
balanced plaintext is P_0(n) = M_0(n) | ~M_0(n).
That value is:
P_0(n) = 0000...00 | 1111...11
and
C_0(n) is a bit-balanced permutation of P_0(n).
Now Eve can use these N/2 + 1 chosen plaintexts and their ciphertexts to
uniquely determine the permutation PI_n() applied to them all using the
relationship PI( A * B ) = PI( A ) * PI ( B ).
The bit-wise XOR of any C_i(n), 1 <= i <= N/2, and C_0(n) is equivalent
to:
C_i(n) XOR C_0(n) = PI_n( P_i(n) XOR P_0(n) )
or
C_i(n) XOR C_0(n) = PI_n ( [ M_i(n)| ~M_i(n)] XOR [ 000..00 | 111..11 ]
);
Let 'Zero' = a string of N/2 0 bits, and let 'One' = a string of N/2 1
bits.
M_i(n) XOR 'Zero' = M_i(n).
M_i(n) XOR ~M_i(n) = 'One'. Therefore 'One' XOR ~M_i(n) = M_i(n).
so, Eve knows that
C_i(n) XOR C_0(n) = PI_n( M_i(n) | M_i(n) ).
The bit-wise XOR of those two ciphertexts produces a ciphertext output
that is equivalent to the ciphertext output of a plaintext string with
just two 1 bit values in it, all other bits 0s, permutated by PI_n().
The XOR of C_i(n) with C_0(n) for all i is equivalent to the ciphertext
produced by applying the permutation PI_n() to plaintext with two
"walking 1 bits" in it.
For example,
C_1(n) XOR C_0(n) = ( 0001...00 | 0100..00 ) = PI_n ( 1000...00 |
1000...00 )
C_2(n) XOR C_0(n) = ( 0100...00 | 0000..01 ) = PI_n ( 0100...00 |
0100...00 )
C_3(n) XOR C_0(n) = ( 0010...00 | 0000..10 ) = PI_n ( 0010...00 |
0010...00 )
.
.
.
C_N/2(n) XOR C_0(n) = ( 1000...00 | 0010..00 ) = PI_n ( 0000...01 |
0000...01 )
The transpositions derived from these equations are ambiguous. In each
of the i cases above, two 1 bit values appear in C_i(n) XOR C_0(n) and
two 1 bits appear in the equivalent plaintext on the right hand side, at
the ith position and the i + N/2 + 1 position in the N bit binary
string.
There are two different ways to transpose the two 1 bits in the
equivalent plaintext string to get the same ciphertext string with two 1
bits.
Eve finally realizes how she can get the equivalent ciphertext output of
a permutation of "walking 1" plaintext that has just a single 1 bit in
it.
For 1 <= i <= N/2, Eve:
ANDs C_i(n) with the (XOR of C_i(n) with C_0(n)) for all i to generate
the ciphertext output expected for the permutation of plaintext with a
"walking 1 bit" moving from the 1st bit position to the N/2 bit position
in the N bit plaintext block.
So the result is
C_i(n) AND (C_i(n) XOR C_0(n)) = PI_n( [M_i(n) | ~M_i(n)] AND [ M_i(n) |
M_i(n)] )
Now M_i(n) AND M_i(n) = M_i(n), M_i(n) AND ~M_i(n) = 'Zero' (a string of
N/2 0 bits.
Therefore,
C_i(n) AND (C_i(n) XOR C_0(n)) = PI_n( M_i(n) | 'Zero' ).
This is what Eve dreamed of getting - only a single 1 bit occurs in the
resulting string on the left hand side. Only a single 1 bit occurs in
the right hand side. So Eve knows where the ith bit in the plaintext
will transpose to in the ciphertext after permutation by PI_n().
For N/2 <= i <= N, Eve:
ANDs the one's complement of C_i(n), ~C_i(n) , with the (XOR of C_i(n)
with C_0(n)) for all i to generate the ciphertext output expected for
the permutation of plaintext with a "walking 1 bit" moving from the N/2
+ 1 bit position to the Nth bit position in the N bit plaintext block.
So the result is
~C_i(n) AND (C_i(n) XOR C_0(n)) = PI_n( [ ~M_i(n) | M_i(n)] AND [ M_i(n)
| M_i(n)] ).
Again, M_i(n) AND M_i(n) = M_i(n), M_i(n) AND ~M_i(n) = 'Zero' (a string
of N/2 0 bits.
Therefore,
~C_i(n) AND (C_i(n) XOR C_0(n)) = PI_n( 'Zero' | M_i(n) ).
This is what Eve dreamed of getting - only a single 1 bit occurs in the
resulting string on the left hand side. Only a single 1 bit occurs in
the right hand side. So Eve knows where the ith bit in the plaintext
will transpose to in the ciphertext after permutation by PI_n().
With these logical formula and N/2 + 1 chosen plaintexts and their
resulting ciphertexts, Eve can uniquely determine the permutation
PI_n().
CRACKING THE KEY (PERMUTATION SEQUENCE) FOR THE SIMPLE DYNAMIC
TRANSPOSITION CIPHER
Using the chosen plaintext attack as described above to determine
PI_n(), Eve can determine every permutation applied to every block for
messages of k blocks length. Eve needs to generate the N/2 "walking 1
bit" bit-balanced blocks and the "zero" bit-balanced block. For each of
the N/2 "walking 1 bit" bit-balanced blocks she repeatedly concatenates
that block k times to make a k block plaintext to pass through the DTC.
For the "zero" bit-balanced block she repeatedly concatenates that
block k times to make a k block plaintext to pass through the DTC.
She uses the resulting N/2 + 1 ciphertext block results (C_i(n)) for the
nth ciphertext block C(n) to solve for the nth permutation PI_n()
applied to the plaintext blocks P_i(n) as above.
I hope this proved interesting, thank you for reading it, it was very
fun to do!
John A. Malley
[EMAIL PROTECTED]
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
