Cryptography-Digest Digest #266, Volume #12 Fri, 21 Jul 00 17:13:01 EDT
Contents:
Re: Question Regarding Encrypting CD-ROM -RW Disks (Greg)
Random Appearance (Future Beacon)
Re: Has RSADSI Lost their mind? (Sander Vesik)
Re: On block cipher and automata (Bryan Olson)
Re: what is the symmetric algorithm for protection of classified info by gov
agencies ? ("Ron Shaffer")
Re: Random Appearance (Paul Koning)
Re: Has RSADSI Lost their mind? (Larry Kilgallen)
Re: help for rc5 cryptanalysis (Anton Stiglic)
Q: Cascading multiple block algorithms (Mok-Kong Shen)
Re: Miller-Rabin-test (Thomas Nordhaus)
Re: Q: Cascading multiple block algorithms (Ichinin)
Re: On block cipher and automata (Terry Ritter)
----------------------------------------------------------------------------
From: Greg <[EMAIL PROTECTED]>
Subject: Re: Question Regarding Encrypting CD-ROM -RW Disks
Date: Fri, 21 Jul 2000 18:57:44 GMT
> Well, wiping a CD of any form is a very different prospect
> from wiping a hard drive, but the old standby of destruction
> by fire is a very viable option, and works quite well on CDs.
This is more true with CDs than HDs. CDs are cheap and they have
a much shorter life time than HDs when the data on them is volatile
over days, weeks, or even months.
But on my laptop, I have a Travelstar 12G drive. I replaced my
4G Travelstar with it. To replace the drive, I simply slid out the
drive caddy, then replaced the drive in the caddy with the 12G.
The point I am making is that with my notebook, and others like it
I am sure, if you had to destroy the HD in a hurry, you could simply
slide it out and go at it with a sledge hammer. These drives are
tiny, thin, and very susceptible to any pressure on their top surface.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Future Beacon <[EMAIL PROTECTED]>
Subject: Random Appearance
Date: Fri, 21 Jul 2000 15:10:21 -0400
All of the encryption methods I have read about in books or here
seem to attempt to make the ciphertext appear random, chaotic, and
meaningless. Does anybody know of an exception that nonetheless
results in strong encryption?
Jim Trek
Future Beacon Technology
http://eznet.net/~progress
[EMAIL PROTECTED]
------------------------------
From: Sander Vesik <[EMAIL PROTECTED]>
Subject: Re: Has RSADSI Lost their mind?
Date: 21 Jul 2000 19:26:57 GMT
Bill Unruh <[EMAIL PROTECTED]> wrote:
> In <[EMAIL PROTECTED]> Sander Vesik <[EMAIL PROTECTED]>
>writes:
>>The patented part affects the usability of the cypher only in areas where
>>it is patented. It is *IMHO* not clear how picking one of the finalists
>>means that it is a "better" cypher in the long run. And at any rate I consider
> presumably the selection process is based precisely on whether one
> cypher is "better" than another. Of course ignorance, incompetence, or
> politics could skew the choice, but also presumably the chances of
> my being better able to make the choice of the best cypher (or even
> deciding that they are roughly equal) is almost non-existant.
I am not qualified to say that they are equally strong - or that one of
them is stronger, and I will probably never be.
But of course, there is the whole matter of what is better. If a set of
the finalists (any number between 2 and 5) can be shown to be equally
strong in the face of all known attacks, then surely the one selected
must be selected based upon other criteria than security? Thus even
though the cypher may be better, but not so under different (possibly
implementation related) criteria.
Which in the end probably means that 5-10 years down the road we are
better off with all 5, not one possibly pretty arbritrary and skewed
final selection.
--
Sander
FLW: "I can banish that demon"
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: On block cipher and automata
Date: Fri, 21 Jul 2000 19:37:14 GMT
[EMAIL PROTECTED] (Terry Ritter) :
[...]
> In practice, the use of "extra data" implies some data expansion, and
> adding significant extra data to each block means we need a large
> block for best efficiency.
The large block is not really necessary. We could use most
of the same randomness across multiple blocks, while mixing
in a little new randomness with each. For example suppose
we're using a 64-bit block. First the sender encrypts one
blocks containing all random bits. The sender and receiver
now share a 64 random vector, call it V.
Now to send the next 63 bits of plaintext,
p = next 63 bits of plaintext
generate a new random bit r
w = concat(p, r)
x = w xor V
c = block_encrypt(x)
V' = first 64 bits of concat(r, V)
The receiver gets c and computes
x = block_decrypt(c)
w = x xor V
p = first 63 bits of w
r = last bit of w
V' = first 64 bits of concat(r, V)
Now the sender and receiver share an updated vector V' which
replaces V. Each block that goes into and out of the
encryption function is uniformly distributed. Blocks more
than 63 blocks apart are independent. The expansion cost
is only one part per 63 plus one block.
We might want a more general framework. Let our blocksize
be B, and we use b bits of randomness per block. We define
three functions on our V vector: update(V, r) combines the
new random data and the current vector; mask(V, w) is of
the form of a block encryption where V is the key; unmask(V,
x) is the inverse of mask(V, w) in the sense that for any
block w, w = unmask(V, mask(V, w)).
Then to send the next B-b bits of plaintext,
p = next B-b bits of plaintext
generate a random b bit vector r
w = concat(p, r)
x = mask(V, w)
c = block_encrypt(x)
V' = update(V, r)
The receiver gets c and computes
x = block_decrypt(c)
w = unmask(V, x)
p = first B-b bits of w
r = last b bits of w
V' = update(V, r)
For more techniques of randomized symmetric encryption, see
"Randomized Encryption Techniques", by Rivest and Sherman in
the proceedings of Crypto 82.
--Bryan
--
email: bolson at certicom dot com
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Ron Shaffer" <[EMAIL PROTECTED]>
Subject: Re: what is the symmetric algorithm for protection of classified info by gov
agencies ?
Date: Fri, 21 Jul 2000 13:44:46 -0500
Amazing how much informtion about crypto gets spewed forth in
this group yet no one here knows crap. The federal government uses
Type 1 encryption modules for all US classified information. The
algorithms are classified but the names are not. Just look on the
Web for any products that are Type 1 certified. Some manufacturers
are Mykotronix, VLSI (now Philips), Racal, Morotola, and L3.
By the way although Skipjack was a classified algorithm it was not
a Type 1 algorithm. It was a Type 2 algorithm. I won't even get into
algorithm. Wouldn't want you guys to actually learn anything.
"jungle" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> FIPS 46-2, The Data Encryption Standard (DES), is the approved symmetric
> algorithm for protection of sensitive but unclassified information by
> government agencies.
>
> what is the symmetric algorithm for protection of classified info by gov
> agencies ?
>
>
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: Random Appearance
Date: Fri, 21 Jul 2000 15:58:02 -0400
Future Beacon wrote:
>
> All of the encryption methods I have read about in books or here
> seem to attempt to make the ciphertext appear random, chaotic, and
> meaningless. Does anybody know of an exception that nonetheless
> results in strong encryption?
Depends on what you mean.
Steganography is a good example: the output looks like
meaningful data, but the encrypted message is hidden inside
that, as close to invisible as can be managed.
paul
------------------------------
From: [EMAIL PROTECTED] (Larry Kilgallen)
Subject: Re: Has RSADSI Lost their mind?
Date: 21 Jul 2000 17:31:02 -0500
In article <[EMAIL PROTECTED]>, Sander Vesik
<[EMAIL PROTECTED]> writes:
> Bill Unruh <[EMAIL PROTECTED]> wrote:
>> In <[EMAIL PROTECTED]> Sander Vesik <[EMAIL PROTECTED]>
>writes:
>>>The patented part affects the usability of the cypher only in areas where
>>>it is patented. It is *IMHO* not clear how picking one of the finalists
>>>means that it is a "better" cypher in the long run. And at any rate I consider
>
>> presumably the selection process is based precisely on whether one
>> cypher is "better" than another. Of course ignorance, incompetence, or
>> politics could skew the choice, but also presumably the chances of
>> my being better able to make the choice of the best cypher (or even
>> deciding that they are roughly equal) is almost non-existant.
>
> I am not qualified to say that they are equally strong - or that one of
> them is stronger, and I will probably never be.
>
> But of course, there is the whole matter of what is better. If a set of
> the finalists (any number between 2 and 5) can be shown to be equally
> strong in the face of all known attacks, then surely the one selected
> must be selected based upon other criteria than security? Thus even
> though the cypher may be better, but not so under different (possibly
> implementation related) criteria.
>
> Which in the end probably means that 5-10 years down the road we are
> better off with all 5, not one possibly pretty arbritrary and skewed
> final selection.
Most people view interoperability as an important goal, which argues
for a single winner.
Some other criteria, such as running on 8 bit processors, are totally
not of interest in particular applications.
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: help for rc5 cryptanalysis
Date: Fri, 21 Jul 2000 16:47:42 -0400
See messages bellow for the context:
I think that if we consider the key schedule to be ideal, we
bump into some problems.
As Wagner pointed, out, the n least significant bits (lsb) of
both halves of the ciphertext depend only on the n lsb of both
halves of the plaintext. More generally, for all operations
on b bit words mixing mod 2^b addition and xor, higher order bits
don't affect lower order bits.
So now, say we want to guess the 1st bit (lsb) of the sub keys
S0, ..., S17.
We can concentrate solely on the 1st bit of all the words and
discard all the other bits. For a specific key K = {K0, ..., K17},
the scheme will encrypt x || b1 and y || b2 to v || bb1 and w || bb2,
where bb1 can only be 1 or 0 (same for bb2),
for all x (the key is fixed and the first bit of each word doesnt
depend on the higher order bits).
So at most, only 4 pairs of (ciphertext, plaintext) can
help us out in guessing the 1st bit of the sub keys. Empirically,
I discovered that it seems like one (plaintext, ciphertext) can help
us discard half of the keys, so instead of having 2^18 possibilities
for the last bits of the sub keys, we have 2^17. A second
(plaintext, ciphertext) pair didn't seem to improve the situation in
the examples I came up with and anything more than 4 pairs would be
redundant as I have explained above.
Without being able to correctly guess the 1st bit, you can't correctly
guess the others. So it seems like you get stuck to being able to
discard only half of the keys. Having X amounts of plaintext-ciphertext
pairs, for X very large, doesn't help improve the situation at all.
In other words, the unity distance seems to be infinity. It looks like
Mark was right on the money when he suspected that the biggest problem
for analysing this cipher would be the amount of plaintext ciphertext
needed.
Did I reason about something wrongly or does this seem right?
Note: I tried playing around with using a key schedule, and trying only
to guess the bits of S0, this seems to be more easy, I think you could
deduce S0 pretty much directly in this case.
Anton
========================================================================
Stanley <[EMAIL PROTECTED]> wrote:
> I know there are many experts in this group. Could anyone help me out
> on cryptanalysis of rc5, with just 8 rounds without any rotations? A
> hint of how to break it will be great. Thanks in advance.
Just to check: the round function, on a pair of words (x, y), is
x = (x ^ y) + k_{2r}
y = (y ^ x) + k_{2r+1}
The key schedule, I'll assume, is ideal, so the k_i are random and
independent.
First observation: a plaintext/ciphertext pair will leak the parity of
the least significant bits of the round keys. You can guess the bottom
bits, and check your guess by trying more significant bits. This is
actually quite a lot of work: there are 16 round key bits to guess at
each stage, although by looking carefully you can work out one of the
bits from the other 15.
Second observation: there's a family of three-round differential
characteristics with probability 1/16. As Knudsen et al. observe in the
analysis of RC2, the actual differentials occur with higher probability,
because the characteristics focus too much on intermediate results.
You can have a good guess at the last two round keys after about 8000
chosen plaintext pairs.
Finally: the biggest problem I see with analysing this cipher is the
large number of equivalent and nearly-equivalent keys there are. You
need a lot of plaintext in order to verify that a key guess consistent
with
one known plaintext actually works with others.
-- [mdw]
David Wagner wrote:
In article <[EMAIL PROTECTED]>,
Mark Wooding <[EMAIL PROTECTED]> wrote:
> Just to check: the round function, on a pair of words (x, y), is
> x = (x ^ y) + k_{2r}
> y = (y ^ x) + k_{2r+1}
> [...]
> Finally: the biggest problem I see with analysing this cipher is the
> large number of equivalent and nearly-equivalent keys there are.
Here's one more. The low n bits of both halves of the ciphertext only
depend on the low n bits of both halves of the plaintext, eek.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Q: Cascading multiple block algorithms
Date: Fri, 21 Jul 2000 23:02:02 +0200
In Schneier's AC, p.367, about cascading two block ciphers it
is stated:
If the second algorithm is vulnerable to a chosen-plaintext
attack, then the first algorithm might facilitate that
attack and make the second algorithm vulnerable to a known-
plaintext attack when used in a cascade.
This isn't very clear for me. In which way can the first
algorithm facilitate the chosen-plaintext attack on the second
algorithm? Since now there is a cascade, the 'known-plaintext'
above must refer to the input to the first algorithm, isn't it?
And the 'chosen-plaintext' certainly refers to the second
algorithm, right? I am confused. Could someone please explain
the issue with a bit detail? Thanks in advance.
M. K. Shen
------------------------------
From: Thomas Nordhaus <[EMAIL PROTECTED]>
Crossposted-To: sci.math.num-analysis,sci.math
Subject: Re: Miller-Rabin-test
Date: Fri, 21 Jul 2000 22:49:13 +0200
Lynn Killingbeck schrieb:
> I don't know about multiplying the actual probabilities (as opposed to
> the 1/4 worst-case), but there is material on the www giving some
> combinations. Try searching for pseudoprimes, then strong pseudoprimes.
> Out of my files, 1,373,653 is a both 2 and 3-SPRP (strong pseudoprime),
> the smallest one.
> 25,326,001 is a 2, 3 and 5-SPRP.
> 2,152,302,898,747 is a 2, 3, 5, 7 and 11-SPRP.
> 3,474,749,660,383 is a 2, 3, 5, 7, 11 and 13-SPRP.
> 341,550,071,728,321 is a 2, 3, 5, 7, 11, 13 and 17-SPRP.
> The first three of these are due to Pomerance, Selfridge and Wagstaff,
> ... and all others are due to Jaeschke. (Note: this
> comment about attribution is an edited cut-and-paste from my web source.
> Wish I still had the URL for your reference, but it's gone from my
> bookmarks, somehow.)
>
> Lynn Killingbeck
Thanks a lot!
I'll try those examples
Thomas Nordhaus
------------------------------
From: Ichinin <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Q: Cascading multiple block algorithms
Date: Fri, 21 Jul 2000 22:55:42 +0200
Mok-Kong Shen wrote:
<Snip>
I think what he is saying is that the strenght of the (cascade)
crypto is as weak as the weakest algorithm.
(why hit a tank from the side when the top armour is weaker?)
/Ichinin
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: On block cipher and automata
Date: Fri, 21 Jul 2000 21:04:36 GMT
On Fri, 21 Jul 2000 11:49:03 +0200, in
<[EMAIL PROTECTED]>, in sci.crypt Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>[...]
>If I understand correctly, I'll summerize the above by saying that the
>state can be a function of the plaintext (in the general case all prior
>blocks) and of random numbers. If we use physical random numbers
>(including online prompt of arbitrary input from the user) these need
>to be output (preferably in scrambled form) to the ciphertext stream
>so that the receiver can use them to get the same state as the sender
>in order to be able to decrypt.
Another approach would be to simply ignore the deciphered
physically-random value, and just use the deciphered plaintext the way
we normally do. That would be pure homophonic operation without
error-detection or authentication. By distinguishing the different
capabilities we can select and mix to get what we want.
The intent is to have a flexible model within which various ciphering
possibilities can be elaborated. The main addition is the concept of
"extra data" or state beyond the usual plaintext. The other addition
is that this "extra data" can be external to the block, within the
block, or both. The model provides a common basis for categorizing a
wide array of apparently different ciphers: Both stream and block
ciphers can be described and compared within the same model, as can
homophonic operation and block-by-block error-checking and/or
authentication.
We can concentrate on any one elaboration of the model, but the model
itself is larger than that.
>In other words, there will be some data
>expansion.
In this case, yes. We get data expansion whenever we put data other
than the plaintext in the block, because less of the block is then
available for plaintext. We get the expansion no matter what we use
that extra data for.
But the general model should support both hidden state as well as
state which is enciphered along with the data, and hidden state does
not expand the ciphertext.
>This expansion may however be justifiable under appropriate
>circumstances.
Right.
>On the other hand, if we use a PRNG, then only a secret
>seed is needed and the ciphertext can be of the same length as the
>plaintext.
That of course is the aspect where "extra data" are not placed in the
block and enciphered, but instead simply select the block operation
performed. That seems to be a form of stream cipher, which is a
natural part of this model.
>The dependence of the transitions on all the prior plaintext blocks
>means in my humble view that we are not simply having a Mealy
>automaton but in addition employing memory to make decisions, i.e.
>we have conceptually something akin to a push-down automaton.
I usually distinguish between systems with "state" or memory and
systems without state. But when I build what I call a "state
machine," I generally plan to do a particular thing in each state.
The general ciphering model can be seen as a state machine, but
differs in that we would probably not define the states specifically,
even in use.
>A simple form of implementation is to use a PRNG to direct the
>processing of a block, i.e. determining the substitutions/permutations
>in it and use some value derived during that computation as feed-back
>to influence the PRNG output. The result is then a block encryption
>that dynamically changes, not simply in a deterministic way (which
>would the case if there were no feed-back to the PRNG) but is
>in a way dependent on the plaintext (I'll roughly call that context
>dependency).
That is certainly one possible system based on the general model. The
ability to elaborate and compare various systems is the advantage.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
** 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 (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
