Cryptography-Digest Digest #552, Volume #13 Fri, 26 Jan 01 02:13:00 EST
Contents:
Durstenfeld Transpositions & ARC4 ("r.e.s.")
Re: Knots, knots, and more knots (Matthew Montchalin)
Re: Durstenfeld Transpositions & ARC4 (Terry Ritter)
Re: Steak Stream Cipher ("Scott Fluhrer")
William's P+1 ("The Death")
Re: What do you do with broken crypto hardware? ("Douglas A. Gwyn")
Re: Durstenfeld Transpositions & ARC4 (David Wagner)
Re: What do you do with broken crypto hardware? (Paul Rubin)
Re: Durstenfeld Transpositions & ARC4 (Paul Rubin)
(EBAY AUCTION) Applied Cryptography (Eric S. Ma)
Re: Cryptographic Camouflage (Thomas Wu)
Re: Durstenfeld Transpositions & ARC4 (Benjamin Goldberg)
Re: What do you do with broken crypto hardware? (Nicol So)
Re: Durstenfeld Transpositions & ARC4 (Benjamin Goldberg)
Integer Primality tests using Chebyshev Polynomials ("ibnsug")
Re: What do you do with broken crypto hardware? (Paul Rubin)
Re: What do you do with broken crypto hardware? (Nicol So)
----------------------------------------------------------------------------
From: "r.e.s." <[EMAIL PROTECTED]>
Subject: Durstenfeld Transpositions & ARC4
Date: Thu, 25 Jan 2001 19:57:58 -0800
In 1964 Durstenfeld published his well-known Shuffle algorithm
that generates a random N-permutation by means of successive
pairwise transpositions, which seems to be the "dynamic" part
of Terry Ritter's "Dynamic Transposition" cipher. Has there
been substantive improvement in such algorithms since 1964, or
does Durstenfeld's remain about as good as any?
Also, is ARC4's byte-stream generator adequate as a CSPRNG? If
so, is there a straightforward way to adapt such a byte-stream
to generate PRNs uniformly distributed on 1..n?
If the answers to these last questions are in the affirmative,
then I wonder whether it might be reasonable to have a 2-stage
cipher that first uses ARC4 as usual (e.g. as in Ciphersaber),
followed by Durstenfeld Transpositions (Shuffles or equivalent)
whose rand(1..n) procedure also uses ARC4's stream. (?)
--r.e.s.
------------------------------
From: Matthew Montchalin <[EMAIL PROTECTED]>
Subject: Re: Knots, knots, and more knots
Date: Thu, 25 Jan 2001 20:18:29 -0800
|Except we have to describe how those bits got there, from the previous
|state. Thus, the punchcard, and what it dictates, is very important.
|
||Also, I'd argue that 10100111 is more complex than either of them.
But the length of the rope has not changed, and by feeding the same
length into this permutation machine, over and over again, you will
eventually reach a repeated state. The number of iterations, N,
defines the true efficiency of the encryption machine.
So, even if you start with a length of rope with knots in such places
represented by the "1" bits, the question is how long it will take
before the rope gets "unknotted" again, thus completing the cycle.
If the rope can be shown to never "unknot" again, then a second
inquiry must be made, and that is how long does it take for the
rope to repeat any given state?
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Durstenfeld Transpositions & ARC4
Date: Fri, 26 Jan 2001 04:59:35 GMT
On Thu, 25 Jan 2001 19:57:58 -0800, in
<94qsjr$qfk$[EMAIL PROTECTED]>, in sci.crypt "r.e.s."
<[EMAIL PROTECTED]> wrote:
>In 1964 Durstenfeld published his well-known Shuffle algorithm
>that generates a random N-permutation by means of successive
>pairwise transpositions, which seems to be the "dynamic" part
>of Terry Ritter's "Dynamic Transposition" cipher. Has there
>been substantive improvement in such algorithms since 1964, or
>does Durstenfeld's remain about as good as any?
There exist other permutation techniques of similar age. Shuffle
seems about as good as any, and is widely understood. For the state
of the art up to 1991, see:
http://www.io.com/~ritter/ARTS/CRNG2ART.HTM#Sect6.7
>Also, is ARC4's byte-stream generator adequate as a CSPRNG?
The ARC4 state is awfully small for Dynamic Transposition, especially
if we shuffle twice. We want more active state in the RNG than is
used in a single encryption, and probably do want at least 128 bits in
the block. Since rejection in Shuffle (to achieve variable-range)
throws away values (and may throw away a lot), probably it is not
large enough.
>If
>so, is there a straightforward way to adapt such a byte-stream
>to generate PRNs uniformly distributed on 1..n?
The conventional technique is "rejection." I have described this many
times. See, for example:
http://www.io.com/~ritter/KEYSHUF.HTM
in "The Shuffling Subsystem" section.
>If the answers to these last questions are in the affirmative,
>then I wonder whether it might be reasonable to have a 2-stage
>cipher that first uses ARC4 as usual (e.g. as in Ciphersaber),
>followed by Durstenfeld Transpositions (Shuffles or equivalent)
>whose rand(1..n) procedure also uses ARC4's stream. (?)
Durstenfeld did not invent bit-permutation ciphers, nor did he invent
the idea of bit-balancing the data for a bit-permutation cipher. That
type of cipher is called Dynamic Transposition.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Steak Stream Cipher
Date: Thu, 25 Jan 2001 20:56:29 -0800
<[EMAIL PROTECTED]> wrote in message
news:94pboj$c1r$[EMAIL PROTECTED]...
> My company has decided to publish the source code
> and a brief documentation of our most recent
> crypto project - a two way error propagating
> stream cipher we pretentiously call Steak
> (because it is both rare and well-done).
>
> the url is http://www.streamsec.com/steak.asp
>
> We would very much appreciate comments,
> questions, suggestions etc of any kind. We have
> been testing the Cipher for some months know, and
> are not done yet. We plan (and hope) to implement
> a final version of this cipher in a secure ftp
> derivate client/server solution later on this
> spring.
If you have any expectation of any kind of realistic analysis done, I
suggest you specify the cipher a bit better. You give some rather vague
block diagrams (e.g. what does "Permute" do? It's never explained AFAICT),
and the only other description is the source, which is largely in x86
assembly language. A mathematical description would be best. Clean
reference code (emphesis on clean) might be acceptable (ANSI C would be my
preference).
--
poncho
------------------------------
From: "The Death" <[EMAIL PROTECTED]>
Subject: William's P+1
Date: Wed, 24 Jan 2001 20:19:57 +0200
I saw several websites, and they all mentioned this algorithm but didn't
have any info about it. Can any1 give me information about this algorithm?
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: What do you do with broken crypto hardware?
Date: Fri, 26 Jan 2001 05:29:29 GMT
Paul Rubin wrote:
> I'm wondering if anyone else here is using crypto hardware modules for
> key management. What do you do if one malfunctions? Throw it into a
> blast furnace? Send it back to the manufacturer for warranty
> repair/replacement, with your secret keys inside? Assume it's broken
> badly enough that you can't program it to securely delete any internal
> keys before sending it for service. You now either have to trash an
> expensive piece of hardware, or decide to potentially compromise your
> keys by sending the dead module to an outside vendor.
There should be a "zeroize" button or else removing the power
should ensure zeroization. The policy document should come
with the hardware, and the local crypto control officer should
be trained in the proper procedures.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Durstenfeld Transpositions & ARC4
Date: 26 Jan 2001 05:35:15 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
r.e.s. wrote:
>In 1964 Durstenfeld published his well-known Shuffle algorithm
>that generates a random N-permutation by means of successive
>pairwise transpositions, which seems to be the "dynamic" part
>of Terry Ritter's "Dynamic Transposition" cipher. Has there
>been substantive improvement in such algorithms since 1964, or
>does Durstenfeld's remain about as good as any?
(I presume this is the standard one, found, e.g., in Knuth.)
No, you can't do any better. Standard lower bounds for sorting
demonstrate that you need O(N log N) swaps to randomly permute
an array of N elements. (This comes from the fact that shuffling
is basically run a comparison-based sort in reverse.)
See Knuth.
>Also, is ARC4's byte-stream generator adequate as a CSPRNG?
Noone knows. But, it is used in >99% of all SSL connections,
so if it's not, lots of SSL transactions are in trouble!
>If so, is there a straightforward way to adapt such a byte-stream
>to generate PRNs uniformly distributed on 1..n?
Any CSPRNG can be used to generate random value uniformly
distributed on 1..n. Many algorithms have been posted here
before.
Here's a simplistic one. Choose k so that 2^k > n.
Let l = n*floor(2^k/n). Using k random bits, generate a
random number from 0..2^k-1; call it x. If x<l, then use
x mod n as your next output value. If x>=l, then repeat
(i.e., keep choosing x until you find one less than l).
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: What do you do with broken crypto hardware?
Date: 25 Jan 2001 21:37:12 -0800
"Douglas A. Gwyn" <[EMAIL PROTECTED]> writes:
> There should be a "zeroize" button or else removing the power
> should ensure zeroization. The policy document should come
> with the hardware, and the local crypto control officer should
> be trained in the proper procedures.
The keys in the modules I'm using are internally stored in flash memory,
so removing power won't erase them. Erasure is a powered operation that
involves writing zeros to the flash, like erasing sectors on a disk.
There's a button on the module that erases the keys, but of course
it's only known to do that if the module is working, and the question
was about what to do when the module is broken. If the module is
broken, the zeroize button might not work.
So what then?
Btw, the module is FIPS 140-1 certified but didn't come with any
policy documents of that type. I suppose I should ask the vendor
how its other customers deal with this question.
Thanks.
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: Durstenfeld Transpositions & ARC4
Date: 25 Jan 2001 21:38:53 -0800
[EMAIL PROTECTED] (David Wagner) writes:
> >Also, is ARC4's byte-stream generator adequate as a CSPRNG?
>
> Noone knows. But, it is used in >99% of all SSL connections,
> so if it's not, lots of SSL transactions are in trouble!
Nah. It's already known that you can distinguish an ARC4 stream from
a random stream by examining about 2**30 bytes of output. That makes
it fair to say it's inadequate as a CSPRNG; but I wouldn't say any SSL
transactions are in trouble as a result.
------------------------------
From: [EMAIL PROTECTED] (Eric S. Ma)
Subject: (EBAY AUCTION) Applied Cryptography
Date: 26 Jan 2001 05:46:45 GMT
Applied Cryptography: Protocols, Algorithms, Source Code in C
Second Edition
Bruce Schneier. Second
ISBN 0-471-11709-9
http://search.ebay.com/search/search.dll?query=applied+cryptography
------------------------------
From: Thomas Wu <[EMAIL PROTECTED]>
Subject: Re: Cryptographic Camouflage
Date: 25 Jan 2001 21:45:51 -0800
Mok-Kong Shen <[EMAIL PROTECTED]> writes:
> Darren New wrote:
> >
> > I.e., it looks like it's protecting against offline searches of passwords
> > you can only truely verify online.
> >
> > Of course, that's just my interpretation. Read the actual patent for what
> > they're actually covering.
>
> Thank you very much. For, trusting that you are right, I don't
> think I would spend time to study the detailed document.
>
> So it seems that it is virtually the 'employment' of a checksum
> that gets patented. When I was in school, solving some systems
Huh? It's just the opposite. Having a checksum (MAC, etc.) that
validates a password guess is exactly what camouflage avoids.
By removing this checksum, and doing some other cleverness, you
get a blob of data that leaks no information about the PIN that
unlocks it. Yet when the right guy comes along with the right
PIN, the correct private key (RSA, DSA, etc.) is constructed and
used. Doing this right involves designing the key formats,
algorithms, and protocols carefully so that this property is
preserved, and that's where the non-triviality comes in.
I happen to work with this technology on a daily basis, so I get
to see those non-trivialities quite often.
Tom
--
Tom Wu * finger -l [EMAIL PROTECTED] for PGP key *
E-mail: [EMAIL PROTECTED] "Those who would give up their freedoms in
Phone: (650) 723-1565 exchange for security deserve neither."
http://www-cs-students.stanford.edu/~tjw/ http://srp.stanford.edu/srp/
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Durstenfeld Transpositions & ARC4
Date: Fri, 26 Jan 2001 05:54:50 GMT
David Wagner wrote:
>
> r.e.s. wrote:
> >In 1964 Durstenfeld published his well-known Shuffle algorithm
> >that generates a random N-permutation by means of successive
> >pairwise transpositions, which seems to be the "dynamic" part
> >of Terry Ritter's "Dynamic Transposition" cipher. Has there
> >been substantive improvement in such algorithms since 1964, or
> >does Durstenfeld's remain about as good as any?
>
> (I presume this is the standard one, found, e.g., in Knuth.)
>
> No, you can't do any better. Standard lower bounds for sorting
> demonstrate that you need O(N log N) swaps to randomly permute
> an array of N elements. (This comes from the fact that shuffling
> is basically run a comparison-based sort in reverse.)
>
> See Knuth.
With the standard Shuffle algorithm, it takes N swaps. The (N log N) is
the number of random bits needed.
--
Most scientific innovations do not begin with "Eureka!" They begin with
"That's odd. I wonder why that happened?"
------------------------------
From: Nicol So <[EMAIL PROTECTED]>
Subject: Re: What do you do with broken crypto hardware?
Date: Fri, 26 Jan 2001 01:08:07 -0500
Reply-To: see.signature
Paul Rubin wrote:
>
> I'm wondering if anyone else here is using crypto hardware modules for
> key management. What do you do if one malfunctions? Throw it into a
> blast furnace? Send it back to the manufacturer for warranty
> repair/replacement, with your secret keys inside? Assume it's broken
> badly enough that you can't program it to securely delete any internal
> keys before sending it for service.
I have worked on systems using secure hardware in key management, but
haven't run into the difficulty you described. (Not that there weren't
any secure hardware failures, but that because of the particular
systems/environments/applications, the failures didn't present a
security problem).
Of the security modules I worked with, none of them was designed to be
repairable (at the module level). For obvious reason, anything that
touches unencrypted keys has to be inside the same protective enclosure
or packaging as the keys themselves. If the security chip(s) fail,
there's hardly anything worth saving in rest of the module. If the
security module is part of an expensive piece of equipment, the sensible
thing to do would be to make the module removable.
With proper design, the dilemma you described is avoidable. Normally,
for a properly designed security module, not even the manufacturer can
extract the secrets from the module. When such a security module fails,
your goal should be to destroy the stored secrets and prevent the
module's functions from being exercised. When preserving the secrets and
repairing the hardware are not the goals, dealing with a failed security
module is not that difficult.
What you want to do with a failed security module is to retire it--stop
encrypting information for it and obsolete any information stored on it.
What you don't want to do is to store global/shared secrets directly in
the non-volatile memory on a security module. Any such secrets should be
stored off the module in encrypted form and loaded in volatile memory
when they are needed. This way, the security module by itself is not
enough to perform any sensitive operation, and can be sent to the
manufacturer for replacement.
> Besides users, do vendors have any policies about this? If I were a
> vendor, I suppose I'd offer as a service option, sending a technician
> out to verify non-functionality of the unit, followed by physically
> disassembling it and removing the key storage elements and leaving
> those elements with the customer, before taking the rest away. Of
> course, getting the key storage parts out of a sealed module might not
> be possible.
Check with your vendor and see what they recommend. Let us know what you
found.
--
Nicol So, CISSP // paranoid 'at' engineer 'dot' com
Disclaimer: Views expressed here are casual comments and should
not be relied upon as the basis for decisions of consequence.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Durstenfeld Transpositions & ARC4
Date: Fri, 26 Jan 2001 06:13:38 GMT
r.e.s. wrote:
[snip]
> Also, is ARC4's byte-stream generator adequate as a CSPRNG? If
> so, is there a straightforward way to adapt such a byte-stream
> to generate PRNs uniformly distributed on 1..n?
There are many ways to make a PRNG produce uniform values 1..n.
Here's two:
This one takes 1 bit at a time from your RNG:
function modran(integer n) {
integer val=0, max=1;
for( ; ; ) {
val = val * 2 + randbit();
max = max * 2;
if( max >= n )
if( val < n )
return val + 1; //you did say 1..n
else {
val = val - n;
max = max - n;
}
}
}
This one uses an RNG which outputs 16 bits at a time:
function modran(integer n) {
integer max = 65536 - (65536 % n);
integer val;
do {
val = ranno();
} while( val >= max );
return val % n;
// or:
return val / (max/n);
// Which one is better depends on the RNG.
}
The bit at a time modran is more efficient in terms of how many random
bits it uses, but if your PRNG outputs many bits at a time, the second
one might be faster.
If your PRNG is very slow, like BBS, then the first might be faster.
I would suggest testing each with the values of 'n' you expect to use,
to find out which is faster.
--
Most scientific innovations do not begin with "Eureka!" They begin with
"That's odd. I wonder why that happened?"
------------------------------
From: "ibnsug" <[EMAIL PROTECTED]>
Subject: Integer Primality tests using Chebyshev Polynomials
Date: Fri, 26 Jan 2001 06:29:55 GMT
1- An odd integer n > 1 is prime if and only if the Chebyshev
polynomial of the first kind T(n,x), divided by x, is
irreducible over the integers.
2- An odd integer n > 1 is prime if and only if T(n,x) = x^n (mod n).
3- The problem of factoring an integer n and the problem of computing
T(n,x) mod n are equivalent.
4- The polynomial T(n,x) can be recursively computed using the formula
T(n,x) = 2*T(m,x)*T(m+1,x) - x for odd n = 2*m + 1
and
T(n,x) = 2*T(m,x)^2 - 1 for even n =
2*m.
If interested in reading more about this, please drop me a note at
[EMAIL PROTECTED] I will be happy to email you a copy of the
technical report conatining the proofs.
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: What do you do with broken crypto hardware?
Date: 25 Jan 2001 22:33:38 -0800
Nicol So <[EMAIL PROTECTED]> writes:
> With proper design, the dilemma you described is avoidable. Normally,
> for a properly designed security module, not even the manufacturer can
> extract the secrets from the module.
Well, nobody is supposed to be able to extract the secrets, but if anyone
can do it, it would be the manufacturer...
> What you want to do with a failed security module is to retire it--stop
> encrypting information for it and obsolete any information stored on it.
> What you don't want to do is to store global/shared secrets directly in
> the non-volatile memory on a security module. Any such secrets should be
> stored off the module in encrypted form and loaded in volatile memory
> when they are needed. This way, the security module by itself is not
> enough to perform any sensitive operation, and can be sent to the
> manufacturer for replacement.
This doesn't make sense--the whole point of the tamper resistant
module is to securely store keys internally. Any keys stored outside
the module are vulnerable to copying and therefore must be encrypted;
but then in order to load them into the module, the decryption key
must be stored inside the module. So if the module is sent back to
the manufacturer, all the keys are potentially compromised.
> Check with your vendor and see what they recommend. Let us know what you
> found.
Yes, will do. Thanks for the thoughts.
------------------------------
From: Nicol So <[EMAIL PROTECTED]>
Subject: Re: What do you do with broken crypto hardware?
Date: Fri, 26 Jan 2001 02:02:43 -0500
Reply-To: see.signature
Paul Rubin wrote:
>
> Nicol So <[EMAIL PROTECTED]> writes:
> > What you want to do with a failed security module is to retire it--stop
> > encrypting information for it and obsolete any information stored on it.
> > What you don't want to do is to store global/shared secrets directly in
> > the non-volatile memory on a security module. Any such secrets should be
> > stored off the module in encrypted form and loaded in volatile memory
> > when they are needed. This way, the security module by itself is not
> > enough to perform any sensitive operation, and can be sent to the
> > manufacturer for replacement.
>
> This doesn't make sense--the whole point of the tamper resistant
> module is to securely store keys internally. Any keys stored outside
> the module are vulnerable to copying and therefore must be encrypted;
> but then in order to load them into the module, the decryption key
> must be stored inside the module. So if the module is sent back to
> the manufacturer, all the keys are potentially compromised.
You're assuming that encrypted versions of these keys are easily
obtainable, which need not be true. Note that these keys are uniquely
encrypted for a particular security module, there's no reason for the
encrypted keys to be floating around. These encrypted keys can and
should be placed under tight control.
--
Nicol So, CISSP // paranoid 'at' engineer 'dot' com
Disclaimer: Views expressed here are casual comments and should
not be relied upon as the basis for decisions of consequence.
------------------------------
** 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
******************************
