Cryptography-Digest Digest #357, Volume #11 Fri, 17 Mar 00 22:13:01 EST
Contents:
Attacks on AES candidates (lordcow77)
Re: NIST, AES at RSA conference ("Trevor L. Jackson, III")
Re: The Breaking of Cyber =?US-ASCII?Q?Patrol=AE?= 4 (David A Molnar)
Re: very tiny algorithm - any better than XOR? (real address at end of post)
Re: Quantum crypto flawed agains Mallory? ([EMAIL PROTECTED])
Re: Maybe public key is more secure ([EMAIL PROTECTED])
Re: Enigma encryption updated (Adam D) ("Joseph Ashwood")
Re: new Echelon article (Jos Horikx)
Re: Lame Question - Please help me out! (Tim Tyler)
Re: Cellular automata based public key cryptography (Tim Tyler)
Re: Cellular automata based public key cryptography (Tim Tyler)
Re: 64-bit Permutations ([EMAIL PROTECTED])
Re: 64-bit Permutations ([EMAIL PROTECTED])
Re: Quantum crypto flawed agains Mallory? ("Joseph Ashwood")
----------------------------------------------------------------------------
Subject: Attacks on AES candidates
From: lordcow77 <[EMAIL PROTECTED]>
Date: Fri, 17 Mar 2000 15:41:25 -0800
Evidently, Schneier and the other cryptographers working with
him have discovered new attacks on the AES candidates. In "A
Performance Comparison of the AES Candidates," Schneier
discusses two new attacks on MARS reduced to 11 rounds in the
cryptographic core and another comprised of the round components
symmetrically reduced to 3 rounds each. Rijndael and Serpent
have distinguishing attacks against 8 and 9 rounds respectively.
I wonder if there are other currently unpublished attacks on the
AES candidates.
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
Date: Fri, 17 Mar 2000 19:24:53 -0500
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: NIST, AES at RSA conference
"Douglas A. Gwyn" wrote:
> Mok-Kong Shen wrote:
> > SCOTT19U.ZIP_GUY wrote:
> > > cause its citazens troulbe as it did the Japanese Americans
> > ... If the authorities could treat citizens of their
> > own countries 'categorically' like that, there appears indeed to
> > be scarcely any foundation to assume that machineries like the
> > Echelon would respect the freedom of privacy of civilians and
> > commercial firms of foreign countries (whether allied, friendly
> > or hostile ones) and refrain from intercepting and analysing
> > their communications.
>
> Different time, different culture, different circumstances,
> different individuals, different legal environment,
> different government. Your conclusion doesn't follow.
Of course it does.
"Those who do not remember the past are condemned to repeat it." - Santayana
Perhaps you would have people forget some of the atrocities conducted upon the
american people by their intelligence agencies in order to further the possibility of
future such events.
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: The Breaking of Cyber =?US-ASCII?Q?Patrol=AE?= 4
Date: 18 Mar 2000 00:25:31 GMT
seifried <[EMAIL PROTECTED]> wrote:
> It reminds me of that database comment someone posted. I would _love_ to run
> a service that distributes information, and when asked to provide logs/etc
> simply say "sorry, I can't do that, they don't exist, and even if you wanted
> me to I couldn't".
Check out the projects listed at http://www.cypherspace.org/links/
for some works in progress aimed at this exact topic.
Thanks,
-David
------------------------------
From: Postmaster@[127.0.0.1] "Spamarang" (real address at end of post)
Subject: Re: very tiny algorithm - any better than XOR?
Date: 18 Mar 2000 00:24:43 GMT
Your instruction space is limited to 50 bytes and crypto-state space is limited
to 30 bytes. What *can* you afford? I think the answer is a large device key,
a fixed S-box, a large IV, and error propagation. (The latter comes from the
assumption that your protocol will do some form of error handling to ensure
that the content was transfered OK.) The S-box can be made part of device key;
in which case, the size of the key with S-box would have to be less than 512
bytes in order to fit in the security-locked on-chip EEPROM. I assume that
there may be other things you will want to put in this EEPROM, so a target key
size is 256 bytes; just enough room for a byte-translation S-box. The 3DES
encryption of this key doesn't have to be secured, so it can be stored in the
external EEPROM. Another asset you have is MIPS. If you overlap the
decryption with EEPROM writes, you should have about 50 us to process each
byte. With the 4MHz AVR part, that is 200 instructions per byte.
Here is a stream cipher suggestion that exploits these assets. You could use an
additive random number generator (ARNG) which needs 6 instructions, 22 RAM
bytes, and 3 registers to implement an ARNG of the form (X_22 + X_1) mod 256.
The RAM locations form a circular buffer that holds X_1 through X_22. One of
the registers holds a copy of X_1, another register ("oldest") holds the
address of the current X_22, and the third register holds a copy of the X_22
value. The constant "base" is the lowest address of the ARNG buffer. The ARNG
uses plain-fed autokey irregular stepping (clocking) and an S-box to add
nonlinearity.
The device key is a 256 byte S-box, which also is used with an IV to initialize
the ARNG state. Of course, the S-box should be balanced. The S-box can be
created during manufacture by permuting the sequence 0 to 255. This gives a
256! key space. The variables "clock" and "X_1" need to be initialized to
arbitrary but known values. These can be whatever happens to be in registers
when a message starts, as long as the values are known by the encryption. If
these are secret, they can be viewed as part of the key as well.
A true random sequence of bytes is attached to the beginning of each message
before encryption. This sequence can be called a secret IV or a session key.
This mechanism eliminates having to restart the decryption algorithm after
receiving a session key. This probably will save you some instruction space.
A zero byte is used to flag the end of the IV. Thus, zeros must be eliminated
from the IV. You can select the number of IV bytes to tradeoff overhead versus
related key analysis susceptibility. For the message size you mentioned, the IV
would be huge; adding just 0.1% overhead to a megabyte message would produce a
thousand bytes of secret IV / session key. Additional restrictions on the IV
that the encryption must enforce are that there must be at least 22 plaintext
ones (guaranteed if 22 or more IV bytes are used) and at least one byte in the
resulting ARNG state must be odd.
For each byte in a message to decrypt, do the following pseudo assembly code.
At the beginning of a message, "init flag" must be a known value that can be
changed by this code and "oldest" must be greater than or equal to "base" + 22.
set the internal EEPROM upper address byte for the S-box's address
next: load next input byte into the "C" register (and post-increment address?)
step: compare "oldest" to "base" + 22
if "oldest" is less than "base" + 22, skip next instruction
load base into "oldest" register
load the "X_22" register indirect through the "oldest" register
compare "init flag" and skip next instruction if not in init
move "clock" to "X_22" register
add "X_22" to "X_1"
store "X_1" indirect through "oldest" and post-increment "oldest"
nostep: store "X_1" into the internal EEPROM lower address byte
set the internal EEPROM read enable bit
load from internal EEPROM data register = "S-box(X_1)"
add "S-box(X_1)" into "C"
add "clock" to itself (or left shift into carry)
jump to "step" if carry flag set
jump to "nostep" if "clock" is not zero
copy "C" to "clock"
xor "X_22" into "C"
compare "init flag" and skip next instruction if not in init
if "C" is not zero, jump to "next"
set "init flag" to not init state
store "C" to plaintext destination and post-increment its address
This should be coded inline to avoid subroutine overhead. These 23 instructions
fit into about 50 bytes. I don't know how many are 3 byte instructions.
This leaks timing information, but I assume that this is not a problem with
your application because the timing is going to be paced by communication speed
and EEPROM write delays (the latter is usually non-deterministic and has a
magnitude that swamps the algorithm's timing variance).
While all you need for your application is authorization, this encryption
(which provides privacy) has smaller instruction size than any authorization
scheme I know.
--
Don'[EMAIL PROTECTED]
Kevin R. Driscoll, Staff Research Scientist PHONE: (612) 951-7263 FAX: -7438
POST: Honeywell M/S MN65-2200; 3660 Technology Drive; Mpls, MN 55418-1006; USA
This leaks timing information, but I assume that this is not a problem with
your application because the timing is going to be paced by communication speed
and EEPROM write delays (the latter is usually non-deterministic and has a
magnitude that swamps the algorithm's timing variance).
While all you need for your application is authorization, this encryption
(which provides privacy) has smaller instruction size than any authorization
scheme I know.
--
Don'[EMAIL PROTECTED]
Kevin R. Driscoll, Staff Research Scientist PHONE: (612) 951-7263 FAX: -7438
POST: Honeywell M/S MN65-2200; 3660 Technology Drive; Mpls, MN 55418-1006; USA
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Quantum crypto flawed agains Mallory?
Date: Sat, 18 Mar 2000 00:31:26 GMT
In article <8au658$328$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Well, the paper is really academical and I lack the required
> training to understand it without studing it very well. I got some bits
> of information, maybe you could help me and comment my conclusions.
> Isn't this paper based in the QKD, which has been proven insecure
> (as stated in Mitra's paper) ?
Mitra was referring to the security aspects
paper (the 1st paper I cited) which gives
experimental reasons for why implementing
actual QKD could be insecure. Theoretically,
the above authentication protocol is provably
secure and is not subject to the man- in- the-
middle attack which (as you correctly
suggested in your first message) threatens
earlier versions of QKD. However, the physical
realization of this protocol might be insecure
due to ,e.g., imperfect detection or
degradation over distances (see security
aspects paper). The weakness of this protocol
as a symmetric cryptographic system could be
overcome by a longer time correlation of
quantum states.
> > Mitra has devised a novel method for ensuring
> > the "absolute security of classical and
> > quantum keys":
> > http://arXiv.org/abs/quant-ph/9912074
> From what I understood, Mitra's technique requires a shared key
> between the legitimate users. How could we exchange this shared key
> securely?
This is done by introducing error into the
elements of the shared sequences without
ruining the bit value of the sequences. This is
possible because the individual bit is
*statistically* encoded. The goal is to use
noise to alter the sequences so that they all
appear identical to the attacker- if the
attacker cannot create meaningful
correlations between the sequences then the
attack must fail. (This is explained in
paragraph 2 on page 4).
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Maybe public key is more secure
Date: Sat, 18 Mar 2000 00:39:38 GMT
In article <8au9nj$5pv$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
>
>
> > I'm under the impression many algorithms will be unaffected, and
> > that moderate increases in key sizes will result in many public-key
> > systems becoming usable again. I don't think it's as bad as all that.
>
> Any algorithm that can be broken by brute force would be affected..
> For example, would a algorithm like Enigma be broken by brute force in
> a Cyphertext only attack? But with the majority of public key
> algorithms (if not all), I think it would.
>
This seems to be true, e.g., it has already been
shown that factoring and discrete log (over
any group including elliptic curves) can be
done in quantum polynomial time.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Enigma encryption updated (Adam D)
Date: Fri, 17 Mar 2000 16:56:34 -0000
> On another note what part of the algy did I not describe
in the doc? I
> described everything incuding how it encrypts the text.
(not just the password)
I think you may have misinterpretted what I wrote. I have
already demonstrated knowledge of your encryption to level
better than your understanding, by posting an equivalent and
vastly superior algorithm. Your description of your password
modification is extremely lacking. If you feel I am wrong,
please feel free to quote from the word document the parts
that I missed.
How did you key RC4? How did you use RC4? Did you ignore the
well known attack on RC4? Did you forget that using good
crypto in a poor way, gives poor security?
As was noted last time, your entire security lies in your
random number generation. I have pointed out exactly where I
fell that it fails, you reveal the entire state on every
byte, and your only claim has been that I do not understand
your method, please point out exactly why.
Joe
------------------------------
From: [EMAIL PROTECTED] (Jos Horikx)
Crossposted-To: alt.politics.org.cia,alt.politics.org.nsa,talk.politics.crypto
Subject: Re: new Echelon article
Reply-To: [EMAIL PROTECTED]
Date: Sat, 18 Mar 2000 01:03:39 GMT
On Fri, 17 Mar 2000 19:09:22 +0100, Mok-Kong Shen <[EMAIL PROTECTED]> wrote
o.a.:
>The following is taken from New Scientist, 11 Mar 00, p.15 :
>
> Intelligence agencies won't have any trouble working out
> how to snoop unnoticed on satellite phone calls. The
> information has just been published in patents filed by
> Motorola in the US and Europe.
Hmm...
Another interesting echelon-article on:
http://cryptome.org/echelon-cia2.htm
Kind regards,
JH
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Lame Question - Please help me out!
Reply-To: [EMAIL PROTECTED]
Date: Sat, 18 Mar 2000 00:52:51 GMT
Kahless42 <[EMAIL PROTECTED]> wrote:
: Does anyone have source code or an algorithm to prove primality or really
: strong pseudoprimality for use in an RSA-type program?
There's Java.math.BigInteger.isProbablePrime(int certainty);
I believe the JDK comes with source code for this function.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
Standards aren't.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Cellular automata based public key cryptography
Reply-To: [EMAIL PROTECTED]
Date: Sat, 18 Mar 2000 01:06:34 GMT
James Felling <[EMAIL PROTECTED]> wrote:
: Tim Tyler Wrote:
:> I don't believe that this follows. A 1D CA can still compute functions
:> which a TM can never compute.
:>
:> The problem with the TM is that it can only do one thing at a time [...]
: Assume that each CA cell in the (countable) line is exactly equivalent to a TM.
: (This is actually NOT true, as the way A CA is constructed a single cell is less
: powerful than a TM.
: The reason that the halting problem is insoluble by a single TM is due to
: the fact that one can always construct a statement that it cannot evaluate.
: This evolves out of Cantor's diagonal argument. You can also do this given
: any N TM's or even a countably infinite collection of TM's, thus even a
: countably infinite number of TM's will NOT beat the halting problem.
: the (countable) 1D line is less powerful than or equal to a countably
: infiniten number of TM's Thus it CANNOT solve the halting problem.
: There will always be some string that it cannot evaluate in finite time.
You're proving something I've never disputed - and indeed positively
asserted - that a 1D CA also can't solve the halting problem.
You have /not/ demonstrated that there are *no* problems which a CA bcan
beat a TM on - only that this *particular* problem is not among them.
As an example of a function which a CA can evaluate, which a TM cannot
ever evaluate, consider a local "blur" function which averages the state
of a few neighbouring cells and outputs the result, over an infinite
domain. A CA computes this rapidly, while a TM can never compute it -
except over a finite domain.
: A (countable) CA cannot do anything that a TM cannot. They are
: equal in power. [...]
We don't agree.
However the argument appears to be becoming tedious - and was never really
on-topic. Can we arrange to draw things to a close somehow?
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
Yo-yos don't.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Cellular automata based public key cryptography
Reply-To: [EMAIL PROTECTED]
Date: Sat, 18 Mar 2000 01:21:07 GMT
Tim Tyler <[EMAIL PROTECTED]> wrote:
: However the argument appears to be becoming tedious - and was never really
: on-topic. Can we arrange to draw things to a close somehow?
/Perhaps/ this will help - to quote from Max Garzon's book:
"Models of Massive Parallelism":
``it is not to hard to prove that a 1D cellular automaton can
[evaluate a specified real function, X()] A Turing machine cannot solve
this problem since the integer 1 could be specified as 0.9999... and
hence the machine cannot even finish reading in its input in a finite
time.'' p. 103.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
The best substitute for experience is being sixteen.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: 64-bit Permutations
Date: 18 Mar 2000 01:37:42 GMT
In a previous article, <[EMAIL PROTECTED]> writes:
[--cut--]
>You're joking, right?
Nope. A non-repetitive sequence of all 2^64 elements in the set of 64 bit
sequences is 64*(2^64) bits long. I am then talking of a permution of 64-bit
_values_.
A permution of 64-bit _positions_ is a completely different story. I expect to
unequivocally determine each such permution from 64 pairs of plain text
cipher text blocks (i.e. from 2x64x8 bytes).
----- Posted via NewsOne.Net: Free Usenet News via the Web -----
----- http://newsone.net/ -- Discussions on every subject. -----
NewsOne.Net prohibits users from posting spam. If this or other posts
made through NewsOne.Net violate posting guidelines, email [EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: 64-bit Permutations
Date: 18 Mar 2000 02:07:07 GMT
In a previous article, Mike Rosing <[EMAIL PROTECTED]> writes:
[--cut--]
>Start with a crib: a set of plaintext-ciphertext pairs. 32 pairs
>should be more than enough to recover the key. You'll have
>an average of 1 bit set and 1 bit clear in each plaintext position
>and you can compare that to the ciphertexts.
[--cut--]
If you are lucky you only need 6 pairs to recover the key: Construct a 6 times
64 bit matrix using the plain text blocks as rows. Read the columns. If all
2^6 numbers are present, you will be able to unequivocally determine the
permutation of each position. (You only have to match the plain text column
with a column of the corresponding cipher block matrix.)
----- Posted via NewsOne.Net: Free Usenet News via the Web -----
----- http://newsone.net/ -- Discussions on every subject. -----
NewsOne.Net prohibits users from posting spam. If this or other posts
made through NewsOne.Net violate posting guidelines, email [EMAIL PROTECTED]
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Quantum crypto flawed agains Mallory?
Date: Fri, 17 Mar 2000 17:13:35 -0000
Actually the statement that Quantum Cryptography can't be
broken has yet to be proven. The proof of Quantum
Cryptography being secure relies on the proof on One Time
Pad. The proof of One Time Pad relies on perfect randomness.
Perfect randomness has not been proven to even exist (at
least not in public), let alone be present ina Quantum link.
Until this is proven, I believe it should be considered
little more than a self-keying stream cipher.
Joe
<[EMAIL PROTECTED]> wrote in message
news:8at30f$8l9$[EMAIL PROTECTED]...
> I've just learned about Quantum Cryptography and how it is
so
> unbreakable... Very interesting indeed!
------------------------------
** 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
******************************
