Cryptography-Digest Digest #694, Volume #11 Wed, 3 May 00 05:13:00 EDT
Contents:
Re: A naive question ("Joseph Ashwood")
Re: A naive question ("Joseph Ashwood")
Re: Cascading Crypto Attack ("Joseph Ashwood")
Re: A naive question (William Rowden)
Re: AEES Advanced ("Scott Fluhrer")
RC5 math (Pred.)
Re: Sunday Times 30/4/2000: "MI5 builds new centre to read e-mails on the net"
(George Edwards)
Re: Command Line Cypher? (Runu Knips)
Re: Silly way of generating randm numbers? (Soeren Mors)
Re: AEES Advanced ([EMAIL PROTECTED])
Re: STU-III (Runu Knips)
Re: The Illusion of Security ("Douglas A. Gwyn")
Re: A naive question (William Rowden)
Re: AEES Advanced ([EMAIL PROTECTED])
Re: Tempest Attacks with EMF Radiation ("Douglas A. Gwyn")
Re: quantum crypto breakthru? ("Douglas A. Gwyn")
Re: Karatsuba threshold (Bo Lin)
Re: STU-III ("Douglas A. Gwyn")
----------------------------------------------------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: A naive question
Date: Tue, 2 May 2000 22:47:02 -0700
> I am afraid that I haven't yet quite understood what you
wrote. To
> repeat my points: If one uses n bits OTP to encrypt, is
that breakable
> or unbreakable?
It is breakable. Brute force will break it, but nothing
else.
> Now use a perfect (brute force only) block cipher
> of n bit key and block size to encrypt, is that breakable
or
> unbreakable?
Breakable, same reason.
Perfection of security is a matter of requiring the attacker
to put at least as much effort into breaking the cipehrtext,
as they would have to in brute forcing a plaintext.
Joe
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: A naive question
Date: Tue, 2 May 2000 22:53:32 -0700
The problem with that theory is that using that theory, a
OTP on top of English is no longer perfect (and the same
qualification should apply to what I responded to Shen),
because there is only 1 bit of entropy per character. This
means that the probability of plaintexts is extremely
slanted. To the point where brute forcing this entire
message would only be a matter of around 400 bits, instead
of the 3200 bits that it should be.
Joe
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Cascading Crypto Attack
Date: Tue, 2 May 2000 23:10:40 -0700
On a techincality you are right. Taking a more generic
approach. As I have stated before in argument against
increasing rounds blindly, and multiple encryption without
analysis. If you take a function f with an output range of
S, within size(S) applications of f on an input you will
recieve the first output, or more importantly for
cryptography (due to the assumed limitations on the
functions) the plaintext will be revealed within size(S)
tests.
There is one problem with this theory for application, the
number involved are astonishingly huge. Let's take a
concrete example of DES, which has an input/output space of
[0,2^64-1], or 64 bits. Now since (almost) any function will
work for the additional applications, we'll use addition of
1 because when applied iteratively it generates each value
in S. On average how many iterations will be needed?
Assumedly with strong crypto this has to be size(S)/2 or
2^63 in our case. That's a big number for most people,
possible though. Extend this to AES and we are forced to
2^127 applications of the function, now I may be somewhat
missing something on this, but I do not see how Quantum
Computing can speed this up (it's inherently linear). The
only option would be to use a parellellizable function of
parameters, reducing our required work for this portion to
2^63.5, maybe better with carefully chosen functions.
However the filtering that must take place next becomes an
additional problem, because we are now treating this as a
One Time Pad, where each input is considered perfectly equal
in probability, quickly leaving the space of usability.
Joe
------------------------------
From: William Rowden <[EMAIL PROTECTED]>
Subject: Re: A naive question
Date: Wed, 03 May 2000 06:06:29 GMT
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> If one uses the k bits as OTP, one commonly says that one can
> encrypt k bits of message with perfect security through XOR, in
> the sense that the analyst can't ever get the k bits plaintext.
Why can't the analyst get k bits of plaintext? It's not due to
computational infeasibility. In the simplest case, a single-bit message
keyed with a *random* single-bit key is still perfectly secure, even
though it is easy to enumerate all possible messages: 0 and 1. The
problem is not computation.
The OTP is theoretically perfectly secure because interception of the
ciphertext has produced no additional information about the plaintext.
For every possible plaintext of length k there exists a key of length k
that could have produced the ciphertext, hence all plaintexts of length
k are a possible solution.
> If one uses the k bits as key to a perfect block cipher to
A block cipher, however, cannot be not "perfect" in the same way that
an OTP can theoretically be perfect (as above). I think this sentence
refers to a block cipher for which the *best* known attack is brute
force, i.e., all *known* attacks take more work than simply enumerating
all possibilities and selecting the one that makes sense in the language
of the plaintext. For this kind of attack, computational feasibility
is the only issue. Beyond a roughly-estimated number of bits one of the
enumerated messages will be highly probable, and all others will be
improbable.
> encrypt n*k bits, one commonly says that one can use brute force
> to get the key and then get the whole n*k bits plaintext.
Here is where the number of bits is relevant. Brute force is useful
mostly when n*k is greater than the unicity distance, or the
uncertainty in the key (H(K)) divided by the redundancy in the language
of the plaintext (D).
> But is it really so? Let n=1.
Then n*k = k. If one assumes maximum ignorance so that H(K) = k, then
k bits is sufficient information to produce a unique solution only if
all k bits are redundant, that is, if there is only one possible
plaintext of length k that therefore has a _a priori_ probability of 1.
If that's the case, one doesn't need brute force.
> This means that the opponent CAN get the k bits plaintext, if he does
> brute force.
No. All brute force will produce in this case is the set of all
possible plaintexts. There would be insufficient information to choose
the correct message.
--
-William
SPAM filtered; damages claimed for UCE according to RCW19.86
PGP key: http://www.eskimo.com/~rowdenw/pgp/rowdenw.asc until 2000-08-01
Fingerprint: FB4B E2CD 25AF 95E5 ADBB DA28 379D 47DB 599E 0B1A
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: AEES Advanced
Date: Tue, 2 May 2000 23:25:05 -0700
<[EMAIL PROTECTED]> wrote in message news:8emr9c$5vv$[EMAIL PROTECTED]...
> AEES is symmetric encryption algorithm, which is developed from the
> DES architecture.
>
> New feature of advanced AEES:
> all permutations used in a round are derived from
> correspondent sub-key.
> This feature provides more entropy and therefor more security.
>
> Features inherited from previous version
>
> 256-bit block
> 16 rounds
> 256 byte key length
> S-box is multiplication table of a group of the order 256
> 16 S-boxes
> 16 sub-keys 256 bytes length
> All S-boxes are derived from sub-keys
>
> All others come from DES architecture.
Which is what? The generic Feistel structure, and the initial permutation?
>
> The Avalanche Effect of advanced AEES.
>
> A desirable property of any encryption algorithm is that a small
> change in either the plaintext or the key should produce a
> significant change in the ciphertext. For 64-bit block DES change
> only one bit gives 34 bit change in ciphertext. This makes 53%.
> To be able to compare current AEES implementation (256-bit) with
> DES (64-bit) we should change the same amount of information namely
> 4 bits. Two ciphertexts encrypted with AEES Advanced differ in 105
> bits, which makes 41%.
How many differ if you change one bit? If much less (or much more) than 50%
change, that probably can be used in an attack -- note exactly which change,
and make guesses on the subkeys based on that.
>
> With two keys that differ in only one bit position in DES
> we have about 50% of the bits in the ciphertext differ.
> In AEES we are using 2048 bits key. To be able to compare
> key avalanche effect with DES we should change 37 bits.
> Again, the results show that about half of the bits in the
> cipher text differ.
Again, what if only 1 bit changes?
>
> Performance mesured with 9,597,349 bytes file and my IP
> II,267 Mhz, 128 Mb is 154 Kb/sec including time for
> all input/output operations.
You do realize that this is dog-slow compared to most modern Ciphers. For
example, Twofish should probably do about 15 MByte/sec on that same platform
(not, however, counting input/output operations)...
>
> Algorithm description and source code can be found
> at <www.alex-encryption.de>
Your description appears to be a Word document. Some of us (including me)
refuse to load an untrusted Word document -- autoload macros can do funny
things. Could you publish it in a straight text format?
--
poncho
------------------------------
From: Pred. <[EMAIL PROTECTED]>
Subject: RC5 math
Date: Wed, 03 May 2000 07:10:13 GMT
Hi!
Is there a paper available that describes RC5 in mathematical terms
including analysis of its strength?
- Pred
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: George Edwards <[EMAIL PROTECTED]>
Crossposted-To:
uk.media.newspapers,uk.legal,alt.security.pgp,alt.privacy,uk.politics.parliament,uk.politics.crime,talk.politics.crypto,alt.ph.uk,alt.conspiracy.spy,alt.politics.uk
Subject: Re: Sunday Times 30/4/2000: "MI5 builds new centre to read e-mails on the net"
Date: Tue, 2 May 2000 19:33:31 +0100
In article <[EMAIL PROTECTED]>, Paul C
<[EMAIL PROTECTED]> writes
>..... and nobody ever heard from him ever again. :-)
Ahem.
--
George Edwards
waiting for the midnight knock on the door
------------------------------
Date: Wed, 03 May 2000 09:51:28 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: Command Line Cypher?
Richard Heathfield schrieb:
> Runu Knips wrote:
> > "Michael J. Fromberger" schrieb:
> > > In <8eieht$550$[EMAIL PROTECTED]> "Jimmy" <[EMAIL PROTECTED]> writes:
> > > >Thanks... the ole XOR encryption... yeah thats pretty secure :)
> > > No! That's not XOR encryption. XOR is totally weak compared to this.
> > > Whereas XOR flips only those bits which correspond to set bits in the
> > > key, this cipher flips ALL the bits of the input! Talk about an
> > > avalanche effect! ;)
> > Avalanche ? Avalance of what ? Stupidity ?
> Death of humour predicted. Film at 11.
Hmm I know I've forgotten the ';-)' after my statement. However,
I've no idea what 'Film at 11' could mean... (no I'm not a native
english speaker).
------------------------------
From: Soeren Mors <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Silly way of generating randm numbers?
Date: 03 May 2000 09:52:15 +0200
[EMAIL PROTECTED] (Bruce) writes:
> In sci.math
> Clive Tooth <[EMAIL PROTECTED]> wrote:
>
> >Anybody interested in files of random numbers should consider George
> >Marsaglia's CD-ROM. See
> >http://stat.fsu.edu/~geo/diehard.html
> >http://webnz.com/robert/true_rng.html
>
> You may also get random number files from www.fourmilab.ch. Look for
> Hotbits, which are generated from a radioactive source of Krypton-85
And lets not forget lavarand.sgi.com
--
Soeren Mors
Student of Computer Science at DAIMI [EMAIL PROTECTED]
For security this message has been encrypted with double ROT13
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: AEES Advanced
Date: Wed, 03 May 2000 07:50:22 GMT
Hi Tom,
#Why 16 rounds? Why not 20 or 4?
DES architecture shows that 16 is optimum number of rounds.
Entropy in cipher text achieves maximum for exactly this number of
rounds.
#Useless. Keys from 80-192 bits is all you really need
#and maybe 256 bits at the max.
Please explain why?
#Explain? Are you doing something like F(a, b) = ab mod 257 ?
No. If I apply automorphism to a cyclic group then law of composition
becomes another form. Correspondent definitions can be found in
algorithm description.
#Static, per round ??? what?
Yes. 16 S-boxes, which are derived from key, are used for substitution
choice in each round.
#Why so big?
Key length relates to internal architecture.
#Are the s-boxes functions?
Law of composition can be considered as function.
#Which is?
I suppose this is simplified DES as described in
William Stallings
Cryptography and network security.
ISBN 0-13-869017-0
#How about differential characteristics? Linear traits?
I suppose a bit better as in DES.
Thank you.
Best regards.
Alex.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
Date: Wed, 03 May 2000 10:02:13 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: STU-III
Doug Stell wrote:
> On Tue, 02 May 2000 17:30:21 GMT, Matt Linder <[EMAIL PROTECTED]> wrote:
> >Does anyone know anything about the algotithim used in STU-III ?
>
> STU-III uses classified, NSA-provided, Type I algorithms. Don't expect
> anyone who knows about them to discuss them in this forum.
What's a STU-III ?? This sounds all mystic...
Type I algorithm ? Hmm sometimes one really wishes to be able to read
other people's mind ! ;-)
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: The Illusion of Security
Date: Wed, 03 May 2000 08:16:47 GMT
Diet NSA wrote:
> In article <[EMAIL PROTECTED]>, "Douglas A. Gwyn"
> <[EMAIL PROTECTED]> wrote:
> >For cryptosystem construction, it is probably the basic
> >*binary* operators that should be considered "linear" or
> >not (for this thread), not *unary* functions, which is
> >the more usual meaning. Without careful clarification
> >of what is meant by "linear" and "composition", time will
> >be wasted in arguing at cross-purposes.
> This is a good point but I was hoping that someone might know of
> a proof or disproof of whether, in the general case, a nonlinear
> function can be composed of a finite number of linear functions.
Sure, and it illustrates my previous point:
L(x) = x is linear, in the usual sense.
L(x)*L(x) is a "composition" in one sense, and is nonlinear
in the usual sense.
If by linear you mean "linear transformation"
and by composition you mean "successive transformations"
then obviously any composition of linears is linear.
------------------------------
From: William Rowden <[EMAIL PROTECTED]>
Subject: Re: A naive question
Date: Wed, 03 May 2000 08:13:31 GMT
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> To repeat my points: If one uses n bits OTP to encrypt, is that
> breakable or unbreakable? Now use a perfect (brute force only) block
> cipher of n bit key and block size to encrypt, is that breakable or
> unbreakable?
Bowing my head to Shannon, I would classify encryption as follows:
"Perfect secrecy" means that interception of ciphertext gives the
attacker no additional information about the plaintext; the
probabilities of each plaintext message given the intercepted ciphertext
(P_E(M)) is identical to the prior probabilities of the plaintext
messages (P(M)). A one-time pad could acheive perfect secrecy.[1]
"Ideal secrecy" or an "unconditionally secure" cipher means that,
although the ciphertext reduces the uncertainty about (equivocation)
the plaintext, no amount of ciphertext will uniquely determine the
key or message (H_C(K)>0 even for large N). I would call these
(and perfectly secret) ciphers "theoretically unbreakable."
I suppose a "conditionally secure" ciphertext would be one that is
shorter than the unicity distance of the cipher, so that the attacker
would have to pick the correct plaintext out of possible false
solutions.
A "theoretically breakable" cipher provides enough information in the
ciphertext to uniquely determine the plaintext. It then becomes
relevant whether determining the plaintext is computationally feasible
(given certain assumptions about complexity and the attacker's
resources).
I'll leave it to someone else to suggest terminology for ciphers
for which the best known attack is trying keys until a key produces
a valid message--a process that requires, on average 2**(k-1), and
at most 2**k trials to find a solution. One may want to distinguish
four cases, corresponding to computationally feasible versus infeasible
as well as "brute force" versus more efficient attacks.
[1] The language of the plaintext is irrelevant to the perfect secrecy
(as defined above) of an OTP. The entropy of that language may be
less than a random sequence; nevertheless, all valid messages are
still possible. All "brute force" provides in this case is the list of
valid messages, which have the same probabilities as they did prior to
interception and analysis.
--
-William
SPAM filtered; damages claimed for UCE according to RCW19.86
PGP key: http://www.eskimo.com/~rowdenw/pgp/rowdenw.asc until 2000-08-01
Fingerprint: FB4B E2CD 25AF 95E5 ADBB DA28 379D 47DB 599E 0B1A
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: AEES Advanced
Date: Wed, 03 May 2000 08:14:49 GMT
Hi Scott,
#Which is what? The generic Feistel structure, and the initial
permutation?
IP, EP, XOR, Substitution, Permutation, inverse to IP.
#How many differ if you change one bit? If much less (or much more)
than
#50% change, that probably can be used in an attack - note
#exactly which change, and make guesses on the sub-keys based on that.
It is not so simple as you imagine. All sub-keys are generated from
inserted
Key due to chain encryption. Each S-box is derived from correspondent
sub-key. All permutations in a round are derived from a sub-key.
#You do realize that this is dog-slow compared to most modern Ciphers.
For
#example, Twofish should probably do about 15 MByte/sec on
#that same platform (not, however, counting input/output operations)...
Modern Cipher says nothing. We can compare only if Modern Cipher
implements the same architecture. Who knows what performance would have
Twofish, which implements the same architecture? For security one should
pay with performance. I am sure that my price is not too expansive.
Thank you.
Best regards.
Alex.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Tempest Attacks with EMF Radiation
Date: Wed, 03 May 2000 08:26:55 GMT
"NFN NMI L. a.k.a. S.T.L." wrote:
> <<In some theories of physics, all particles are described as
> vibrating instances of energy.>>
> Quack or unproven ones.
There is certainly (bound) energy in every particle.
Not that it matters at the level the fellow was talking.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: quantum crypto breakthru?
Date: Wed, 03 May 2000 08:51:35 GMT
> By JAMES GLANZ
> Among other things, Einstein showed that, according to quantum
> mechanics, measuring one particle could instantly change the properties
> of another particle, no matter how far apart they were. He considered
> this apparent action-at-a-distance, called entanglement, too absurd to
> be found in nature, and he wielded his thought experiments like weapons
> to expose the strange implications that this process would have if it
> could happen.
> But experiments described in three forthcoming papers in the journal
> Physical Review Letters give a measure of just how badly Einstein has
> been routed. The experiments show not only that entanglement does happen
I wish reporters wouldn't "explain" things incorrectly.
He's talking about the EPR paradox, and the key to understanding
it is that Einstein's intuition against action at a distance was
*right* -- information is *not* transmitted "instantaneously" nor
faster than light. One doesn't even need quantum principles to
exhibit a kind of EPR paradox: just take two synchronized, highly
accurate clocks to distant locations, then look at the second hand
on one of the clocks. Before making the observation, you had no
knowledge of the state of the second hand on the remote clock,
but when you make the observation, you know with certainty what
the second hand reads on the remote clock at the same instant (as
determined in the common inertial frame for both clocks). The
peculiar part of EPR is only that quantum physics provides a way
to maintain synchronization between two parts of a single system
(the "entanglement"). Learning to work with entanglements when
they are almost everywhere is the hard part of the "philosophy"
involved with EPR etc., because we're not used to that situation
in everyday life. The real puzzle is why pure states aren't the
same as mixed states.
------------------------------
From: Bo Lin <[EMAIL PROTECTED]>
Subject: Re: Karatsuba threshold
Date: Wed, 03 May 2000 09:42:04 +0100
This topic remind me of the work in 1980s to implement RSA with a 8088
CPU. I compared the classical, Karatsuba, and Toom-Cook to multiply two
integers. Karatsuba beat the classical when the number of 16-bit words
is about 10. So one can write an 8-word classical as a base multiplier
then apply Karatsuba recursively. If you have a fast multiplier, say, a
6MHz 80286 at that time, Karatsuba beat the classical at the number of
16-bit words about 24. Again, one can write a 24-word classical as a
base multiplier then recursively apply Karatsuba. I believe it is very
difficult for Karatsuba to beat the classical with modern CPUs and the
Montgomery reduction now.
In terms of Toom-Cook, it was a little bit disappointing since I thought
it should be the fastest one. I wrote a 512-bit x 512-bit routine and it
took about 1 ms to get the result. I analyzed the implemetation and
found that there are many small number mutiplying and dividing (x 1, x
2, ..., /1, /2, ...) which I had to implement them with the 8088
multiplier and divider because it was faster than doing it with shift
with addition or shift with subtraction. This caused the "real"
reference of multiplier and divider much more than the "contributing"
reference. Toom-Cook could be a good method for hardware design but not
for software implementation. However, I would like to encourage you to
write a piece of program to verify Toom-Cook which was marked 40 in
Knuth's 1969 version and upgraded to 42 in the lastest version. It won't
take you too much time.
One of my friends wrote Schonhage-Strassen with Fortran on a IBM360. It
was hopeless. This was why I didn't do anything about it.
Bo Lin
Motorola Limited
Email: [EMAIL PROTECTED]
Francois Grieu wrote:
>
> I assume we multiply two numbers of n*w bits each, giving a result of
> 2*n*w bits (at most) with a general purpose computer of word size w
> bits, with hardware that can multiply two w bits integers giving a 2*w
> bits integer in a few cycles.
>
> The classical multiplication algorithm performs n^2 multiplications and
> has execution time O(n^2)
>
> The Karatsuba multiplication method [1] (or variants [2]) has execution
> time O(n^1.5)
>
> Above some threshold for n, Karatsuba multiplication beats classical
> multiplication, and I am seeking experimental estimations of this
> "Karatsuba threshold".
>
> GMP defaults to a KARATSUBA_THRESHOLD of 8, but Knuth says 2 on most
> architectures. Any other estimations out there ?
>
> Also, what are the next thresolds, like when does Toom-Cook [3] or FFT
> multiplication [4] becomes usefull ?
>
> Francois Grieu
>
> [1] <http://mathworld.wolfram.com/KaratsubaMultiplication.html>
> [2] Knuth TAOCP Vol 2, 4.3.3 A
> [3] Knuth TAOCP Vol 2, 4.3.3 Alg T
> [4] Knuth TAOCP Vol 2, 4.3.3 C
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: STU-III
Date: Wed, 03 May 2000 09:09:10 GMT
Runu Knips wrote:
> What's a STU-III ?? This sounds all mystic...
> Type I algorithm ? Hmm sometimes one really wishes to be able to read
> other people's mind ! ;-)
I think Doug Stell was assuming that anyone who asked the
question would understand the terminology.
STU III -- a secure telephone, using a "crypto ignition key"
to authenticate the user, with a centralized Key Management
Center located in Maryland. A newer secure telephone (with
backward compatibility) is supposed to be fielded soon.
Type I encryption -- high-grade encryption authorized by
NSA/CSS for protection of the most sensitive information.
A Type I algorithm is designed to withstand the best
cryptanalytic efforts expected for several decades.
------------------------------
** 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
******************************
