Cryptography-Digest Digest #245, Volume #14 Fri, 27 Apr 01 02:13:00 EDT
Contents:
Re: ANOTHER REASON WHY AES IS BAD ("Tom St Denis")
Re: LFSR Security (Benjamin Goldberg)
Re: Security proof for Steak ("Henrick Hellstr�m")
Re: LFSR Security (Benjamin Goldberg)
Re: RC4 Source Code ("r.e.s.")
Re: Announcing A New Rijndael Encryption Algorithm Implementation ("JGuru")
Re: RC4 Source Code ("Dirk Mahoney")
Re: Graphical representation of a public key (or fingerprint)? (Paul Crowley)
Re: AES poll (Paul Crowley)
----------------------------------------------------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: ANOTHER REASON WHY AES IS BAD
Date: Fri, 27 Apr 2001 04:11:30 GMT
=====BEGIN PGP SIGNED MESSAGE=====
Hash: SHA1
"Tim Tyler" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Tom St Denis <[EMAIL PROTECTED]> wrote:
> : "SCOTT19U.ZIP_GUY" <[EMAIL PROTECTED]> wrote in message
> :> [EMAIL PROTECTED] (Darren New) wrote in
> <[EMAIL PROTECTED]>: :> >SCOTT19U.ZIP_GUY wrote:
>
> :> >> Actaully Tom as usually your quite wrong. If one looks at
> an OTP :> >> you would have to think of the OTP data itself as part
> of the :> >> encryption program or the program nesicessary to make
> the OTP sting. :> >
> :> >So why do you think that doesn't apply to the AES cyphers as
> well? :>
> :> Actaully I do think it should inculde the AES short keys of
> 256 bits. :> Why do you think I mentioned scott19u and its key
> which is over a :> million butes in length. [...]
>
> : Why is a 256-bit key too short?
>
> It's short compared to the OTP key or the scott19u key discussed.
>
> "Too short" was not mentioned - except by you.
Now you're being an idiot. he says "Actaully I do think it should
inculde the AES short keys..." [sic] to me that suggests that an AES
key is too short. What else does it mean?
And why is a million byte scott19u key any better? If I can break is
algorithm with say (just for example) 2^20 texts and 2^40 work, then
a 1000000 bit key is not the sign of strength.
At least AES has been cryptanalyzed as compared to someone elses
method. And while it is true cryptanalysis is never done, *some*
_is_ better than *none*.
Tom
=====BEGIN PGP SIGNATURE=====
Version: PGPfreeware 7.0.3 for non-commercial use <http://www.pgp.com>
Comment: Key at: http://tomstdenis.home.dhs.org/key.asc
iQA/AwUBOujxcQULrT+pXe8cEQKPdQCfREsDhr8ySSQYMLYHnPCbZI1wHAEAoOB5
EQM/ZnFnVOhuaQWEjgMA4eC7
=q19t
=====END PGP SIGNATURE=====
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt.random-numbers
Subject: Re: LFSR Security
Date: Fri, 27 Apr 2001 04:26:20 GMT
Trevor L. Jackson, III wrote:
>
> Ian Goldberg wrote:
>
> > In article <[EMAIL PROTECTED]>,
> > Trevor L. Jackson, III <[EMAIL PROTECTED]> wrote:
> > >With N unknown you just use Berlekamp-Massey. The invariant in BM
> > >is that one always has the smallest configuration that explains the
> > >sequence up to the current bit. By continuing this process through
> > >the gaps, assigning each unknown bit the subsequent output of the
> > >current machine, one can maintain the invariant and preserve the
> > >validity of the result.
> >
> > So after reading this thread this morning, I spent the day studying
> > the BM algorithm. I now Understand it.
> >
> > The above isn't true. For example, find the LFSR that generates:
> >
> > 1 0 0 0 ? 0 ? 0 1 1
> >
> > The answer is actually the LFSR of size 5: 111101 which generates
> >
> > 1 0 0 0 1 0 1 0 1 1
> >
> > But if you use Trevor's technique, you get that after the first 4
> > bits, you're working with the LFSR of size 1: 10 which generates
> >
> > 1 0 0 0 0 0 0 0 0 0 ...
> >
> > and you'll only see a problem when you get to the 1's at the end,
> > at which point you're forced to change it to the LFSR of length 8:
> > 110000001.
>
> Not quite. You can assume that the most recent known bit is the
> culprit, as in your example, but there's no reason to prefer that bit,
> and good reason to believe that the culprit is earlier in the
> sequence.
Not only is there no reason to assume that it's the most recent known
bit, there is no reason to believe that the culprit is earlier either.
> So when a conflict is found one must backtrack by trying
> (toggling) each of the assumed bits in turn and use the smallest
> machine created.
This reduces to brute force (ie, exponential work) on the assumed bits.
To me, this indicates that the method is flawed -- we should have a way
of doing it without having to make any assumptions about the bits.
Suppose that we learn that the 1st, 57th, 61st, 90th bits are zero, and
the 43rd, 100th, 201st and 1000th are zero. Surely there is some
algorithm which can do this without having to make 992 assumptions about
unknown bits, and then have to go back and flip them.
[snip]
> > i.e. the "Greedy Algorithm" isn't optimal.
>
> There's a terminology conflict here. First we need correctness. Then
> we need efficiency. The technique you analyzed is not correct (did
> not produce the smallest machine). An optimal algorithm would produce
> the smallest machine is as few steps as possible.
And even if it were correct, it would be exponential in the number of
unknown bits, which can be much much greater than the number of taps in
the LFSR.
Here's a functional algorithm for finding the LFSR taps and state with
known but irregular gaps.
for L in (1 to #known bits) {
foreach p in (all LFSR polys length L) {
foreach B in (known bits)
z[B] = x ** B.position mod 2 mod p
// note that x above is the polynomial "1*x^1 + 0*x^0"
foreach i in (all initial states length L) {
foreach B in (known bits) {
if( i * z[B] mod 2 mod p != B.value )
next i
}
return (p,i)
}
} }
I believe that this takes O(2**(2N)) time, where N is the number of
known bits. An algorithm which does backtracking will take exponential
time wrt the sizes of the gaps... and gaps can be 1000s of bits big.
--
Sometimes the journey *is* its own reward--but not when you're trying to
get to the bathroom in time.
------------------------------
From: "Henrick Hellstr�m" <[EMAIL PROTECTED]>
Subject: Re: Security proof for Steak
Date: Fri, 27 Apr 2001 06:26:26 +0200
"Henrick Hellstr�m" <[EMAIL PROTECTED]> skrev i meddelandet
news:9c69h0$o1h$[EMAIL PROTECTED]...
> Actually, this property seems to be irrelevant. Regardless if the Steak
> matrix or an MDS matrix is used, for each of the four bytes exactly one
> column of the 4 by 256 dword matrix representation is zero in any of the
> four output bytes. Hence, if you add random single cycle permutation
sboxes
> any one byte differential will in both cases result in any output
> differential after at most four iterations.
I must have been tired when I wrote that. ;-)
What I wrote implies that for each single byte input differential D and each
output differential O, you could find an input value X such that F(X) xor
F(X xor D) = O, but that's neither possible nor desirable. However, you do
want there to be in almost all cases an input value X and a key K such that
E_K(X) xor E_K(X xor D) = O, and that's what will happen when the sboxes are
added.
In fact, for each X, D and O there is such a key K. There is even a high
probability to find such a key if only two iterations are made, because any
single byte input differential will result in a four byte output
differential, so you will in such case obtain the result simply by assigning
proper values to three of the positions in each sbox. Due to the key
schedule this choice is more or less arbitrary, and the probability of a
collision is low, because you can mostly ward off a collision at the second
iteration by altering the selection at the first.
The only "impossible differentials" would be those that strictly require
that you place the same value at two different positions in the same sbox,
and those that would give rise to a short cycle. For example, if D is
non-zero, then O cannot be zero after any number of iterations.
--
Henrick Hellstr�m [EMAIL PROTECTED]
StreamSec HB http://www.streamsec.com
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt.random-numbers
Subject: Re: LFSR Security
Date: Fri, 27 Apr 2001 04:33:35 GMT
Gregory G Rose wrote:
>
> In article <bw3C6.8369$[EMAIL PROTECTED]>,
> Tom St Denis <[EMAIL PROTECTED]> wrote:
> >Question: Does the BM algorithm apply when non consecutive outputs
> >are known?
>
> A regular decimation (say, every 3rd output) of an
> LFSR is another LFSR. B-M will apply to that. If
> the decimation doesn't divide the period of the
> original LFSR, you can get it back entirely.
As has been said, the real problem (new problem?) is *irregular* (but
known) decimation of an LFSR. This is generally not another LFSR.
> If you know the taps and where the bits came from,
> then David's solution works anyway, the equations
> just get more complicated.
And if we know where the bits came from, but not the taps, what then?
--
Sometimes the journey *is* its own reward--but not when you're trying to
get to the bathroom in time.
------------------------------
From: "r.e.s." <[EMAIL PROTECTED]>
Subject: Re: RC4 Source Code
Date: Thu, 26 Apr 2001 21:41:21 -0700
"Bill Unruh" <[EMAIL PROTECTED]> wrote ...
[...]
| One can point to the ARC4 source code and state that tests have shown
| that on a selected set of inputs, the output of ARC4 is identical to
| RC4. One cannot say that it is identical since noone knows.
Whoever reverse engineered RC4 to obtain ARC4
probably does know that they are identical, imo.
--r.e.s.
------------------------------
From: "JGuru" <[EMAIL PROTECTED]>
Subject: Re: Announcing A New Rijndael Encryption Algorithm Implementation
Date: Fri, 27 Apr 2001 04:56:27 GMT
AES is a symmetric cypher, so any client on the chat needs to have every
other clients passphrase to decrypt the message. For each client to get
another clients passphrase you must somehow exchange that passphrase over
the network. How are you doing that? You need more than a symmetric cypher
to do this securely. I have a java implementation of a chat that is truly
secure. For one, I will give to anyone for free. For two, I will also
include the source. And three, I would explain how it works and why it's
secure, but I would probably just give you ideas on how you should have
implemented your program.
"bloopa" <[EMAIL PROTECTED]> wrote in message
news:He8C6.15694$[EMAIL PROTECTED]...
> VSpace Encrypted Chat
>
>
>
> Note: This version of VSpace Encrypted Chat is a complimentary release and
as
> such only provides 32-bit encryption. This version is free from use
> restrictions. Please contact [EMAIL PROTECTED] for information on how
to
> obtain a 256-bit encryption release.
>
>
> http://www.vspacecorp.com/vschat2.zip
>
>
> Warning
> This program is not intended for use outside of the United States or by
> private individuals. Severe penalties will be assessed if you are
investigated
> and found to be in possession of this Cipher System. Only approved
> Corporations and Government Agencies may use VSpace Encrypted Chat.
>
>
>
> VSpace Encrypted Chat is a secure communications platform that was
designed to
> protect sensitive conversations from intelligence gathering. VSpace
defines
> intelligence gathering as data mining by:
>
>
>
> � Hostile Governments
>
> � Foreign Armed Services
>
> � Foreign Nationals
>
> � Hostile Religious Organizations
>
> � Corporate Spies
>
> � Industrial Espionage
>
> � Russian and Ukrainian Mafia
>
> � International and Domestic Terrorists
>
> � Former Employees
>
> � Internet Hackers
>
>
>
> The threat to your security is very real. Simply inspect your firewall
records
> to convince yourself.
>
>
>
> What makes VSpace Encrypted Chat so secure?
> Under the United States Federal Regulations concerning domestic
encryption,
> all cipher systems intended for public use must be inspected and approved
by a
> government agency. These systems must also have a documented back door so
that
> law enforcement will be able to break the cipher.
>
>
>
> These rules do not apply for private corporations and government agencies.
> VSpace Encrypted Chat does not contain any back doors. This freedom from
> restrictions also allowed us to develop and insert into VSpace Encrypted
Chat
> a unique implementation of the Rijndael Encryption Algorithm that defeat
all
> known attacks.
>
>
>
> VSpace Rijndael Implementations
>
>
> Rijndael
> The default encryption algorithm that VSpace Encrypted Chat uses is
straight
> Rijndael. This is where you supply a password at the beginning of your
session
> and all sentences are encrypted with the same key that was generated from
that
> password for the duration of the session.
>
>
>
> This method is very secure; especially when using 256 bit keys which is
also
> the default. However, VSpace doesn't like to anything normally. They set
out
> to make it even stronger, if it were possible.
>
>
>
> Rijndael Plus
> This is VSpace's proprietary implementation of the Rijndael algorithm that
> completely renders harmless all known attacks. This is where you supply a
> password at the beginning of the session and from that point on every
letter
> that you type is treated as its own document and is encrypted with its own
> unique password that was spawned from the original. If your sentence
contains
> 50 characters including spaces and periods, Rijndael Plus will produce 50
> separately encrypted documents that were made from 50 separate passwords!
>
>
>
> Just trying to crack "Mary had a little lamb" this way would use more
> resources than the value of the data received. Imagine how difficult it
would
> be to determine exactly where to look into a conversation between three or
> more individuals for the intelligence that you are seeking? Especially
when
> the printed cipher text may be 10mb or larger?
>
>
>
> If you were to guess correctly the password, it would do you no good
without
> knowing exactly what to do with that password now that you have it. The
> original password is never used to generate keys. It is used to spawn
other
> passwords that will generate keys.
>
>
>
>
>
>
>
>
>
>
>
>
>
> The Encrypting Rijndael Algorithm - AES
>
> Rijndael algorithm
>
> The Rijndael algorithm, also known as an Advanced Encryption Standard
(AES),
> is used for encryption and decryption of files and text.
>
> Rijndael is an iterated block cipher with a variable block length and a
> variable key length. The
> block length and the key length can be independently specified to 128, 192
or
> 256 bits.
>
> The Advanced Encryption Standard (AES) will be a new Federal Information
> Processing Standard (FIPS) Publication that will specify a cryptographic
> algorithm for use by U.S. Government organizations to protect sensitive
> (unclassified) information. NIST also anticipates that the AES will be
widely
> used on a voluntary basis by organizations, institutions, and individuals
> outside of the U.S. Government - and outside of the United States - in
some
> cases. NIST has selected Rijndael as the proposed AES algorithm.
>
> You can learn more about the Rijndael algorithm and AES at:
>
>
>
> � http://csrc.nist.gov/encryption/aes/
>
> � http://www.nist.gov/public_affairs/releases/g00-176.htm
>
>
>
> Why did NIST select Rijndael to propose for the AES?
>
> When considered together, Rijndael's combination of security, performance,
> efficiency, ease of implementation and flexibility make it an appropriate
> selection for the AES. Specifically, Rijndael appears to consistently
perform
> well in both hardware and software across a wide range of computing
> environments regardless of its use in feedback or non-feedback modes. Its
key
> setup time is excellent, and its key agility is good. Rijndael's very low
> memory requirements make it very well suited for restricted-space
> environments, in which it also demonstrates excellent performance.
Rijndael's
> operations are among the easiest to defend against power and timing
attacks.
>
>
>
> Additionally, it appears that some defense can be provided against such
> attacks without significantly impacting Rijndael's performance. Rijndael
is
> designed with some flexibility in terms of block and key sizes, and the
> algorithm can accommodate alterations in the number of rounds, although
these
> features would require further study and are not being considered at this
> time. Finally, Rijndael's internal round structure appears to have good
> potential to benefit from instruction-level parallelism.
>
>
>
> AES key sizes
> The AES will specify three key sizes: 128, 192 and 256 bits. In decimal
terms,
> this means that there are approximately:
>
> 3.4 x (10^38) possible 128-bit keys;
>
> 6.2 x (10^57) possible 192-bit keys; and
>
> 1.1 x (10 ^77) possible 256-bit keys.
>
> What is the chance that someone could crack an AES key?
> Assuming that one could build a machine that could recover 255 keys per
> second, then it would take that machine approximately 149 thousand-billion
> (149 trillion) years to crack a 128-bit AES key. To put that into
perspective,
> the universe is believed to be less than 20 billion years old.
>
>
>
> What about the other four algorithms that were not selected?
>
> In terms of security, NIST states in its report that "all five algorithms
> appear to have adequate security for the AES." NIST is not saying that
there
> is anything "wrong" with any of the other four algorithms. However, when
all
> of the analysis and comments were taken into consideration, the NIST team
felt
> that Rijndael was the best selection for the AES.
>
>
>
> Adequate security, conformed by NIST, is the reason why VSpace Encrypted
Chat
> implements the Rijndael algorithm for its encryption.
>
>
>
>
>
>
------------------------------
Reply-To: "Dirk Mahoney" <[EMAIL PROTECTED] (remove the _)>
From: "Dirk Mahoney" <[EMAIL PROTECTED] (remove the _)>
Subject: Re: RC4 Source Code
Date: Fri, 27 Apr 2001 05:17:54 GMT
Mark,
Sorry for wasting your time. After doing some searches and failing, I
thought the next best plan was to ask in the newsgroup to which the original
code was leaked. Seems logical to go straight to the source when all else
fails. If you ask me, it seems logical to go straight to the source to
begin with to avoid *wasting time*, but I didn't.
I had no idea such a simple question would cause me to be flamed.
All searches I did yielded lots of nothing. RSA's site obviously had
nothing, couldn't find anything in the sci.crypt FAQ, Counterpane's site
wasn't helpful, neither was Rivest's (for obvious reasons), Terry Ritter's
or Matt Blade's. I thought that if I was to find something then these would
be the places.
You have my most sincere apologies for wasting your time. I didn't mean to
disturb your quiet reading of sci.crypt. But please remember, if you feel
I'm wasting your time, no-one's forcing you to reply to my posts. Please
take my apology in the spirit in which it was intended - sincerely.
And I apologise to Tom St Denis for being rude to him after he told me I was
useless at coding without knowing my background.
- Dirk
"Mark Wooding" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Dirk Mahoney <[EMAIL PROTECTED]> wrote:
>
> > Thank-you for that friendly and helpful reply. If I had a description
> > handy, I probably would have coded it. I hope all newcomers to
sci.crypt
> > aren't 'spoken' to like that.
>
> That's more than a little rich, coming from someone who clearly hasn't
> even made the effort to try a few simple expressions in a search
> engine.
>
> I hope that most other newcomers are better mannered than to waste our
> time with questions they can answer themselves and then complain at us.
>
> -- [mdw]
------------------------------
Subject: Re: Graphical representation of a public key (or fingerprint)?
From: Paul Crowley <[EMAIL PROTECTED]>
Date: Fri, 27 Apr 2001 05:33:25 GMT
"Michael Schmidt" <[EMAIL PROTECTED]> writes:
> I know that there has been research on the topic "graphical passwords", i.e.
> keys being created from graphical user input.
>
> I'm wondering whether there has been any research conducted on the topic
> "graphical representation of a public key" or the key's fingerprint. My goal
> is to authenticate a public key (or better: its fingerprint, like with PGP)
> securely by creating and comparing its graphical representation with an
> "original", which is unique enough for every key/fingerprint, yet easy to be
> processed and compared by the human brain.
I've thought for a while that some sort of IFS-based picture generator
would be the right way to do this. The IFS screensaver that comes
with "xscreensaver" seems to generate a huge variety of interesting
patterns while mostly avoiding the boring ones, which is a hell of a
trick. That's open source, so it might be worth looking at how it's
done.
This would be a really useful project - you could print the graphic on
business cards, and check people's public keys in the blink of an eye!
I hope you get somewhere with it.
--
__ Paul Crowley
\/ o\ [EMAIL PROTECTED]
/\__/ http://www.cluefactory.org.uk/paul/
"Conservation of angular momentum makes the world go around" - John Clark
------------------------------
Subject: Re: AES poll
From: Paul Crowley <[EMAIL PROTECTED]>
Date: Fri, 27 Apr 2001 05:33:25 GMT
Benjamin Goldberg <[EMAIL PROTECTED]> writes:
> More like, the twofish team said, our cipher is very secure, and these
> other two ciphers are about as secure as ours (maybe a tiny fraction
> less secure, but not so much that it's noticable). But the people doing
> benchmarks said, Rijndael is fastest. And since there wasn't any
> security reason *not* to use Rijndael, and there *was* a indication that
> Rijndael would be faster, the decision was to use Rijndael.
Actually, Twofish was faster on some platforms (eg Pentium). And they
voiced concerns about the number of rounds in Rijndael - Schneier in
his final presentation said he wanted it extended to 18. I think
Rijndael won out over Twofish because its simplicity made it easier to
feel that we'd found out a lot about it during the limited period for
analysis.
As processors get more parallel, Rijndael gets more of an edge over
Twofish. So you could say it was a forward-looking choice.
> IIRC, the twofish team considered theirs to be securitywise better than
> all of the other 4, and considered serpent and rijndael to come closest
> to it in strength.
I'm not sure that's true; pretty much everyone agreed that Serpent had
the biggest security margin. And MARS and RC6 fell down not so much
on security, but on resource demands outside the Pentium platform, eg
on smart cards and in hardware. Both were also too difficult to
analyze, and RC6 had a relatively worrying security margin.
--
__ Paul Crowley
\/ o\ [EMAIL PROTECTED]
/\__/ http://www.cluefactory.org.uk/paul/
"Conservation of angular momentum makes the world go around" - John Clark
------------------------------
** 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
******************************
