Cryptography-Digest Digest #652, Volume #13 Wed, 7 Feb 01 18:13:01 EST
Contents:
Re: relative key strength private vs public key (Tom St Denis)
Re: Pseudo Random Number Generator (Mok-Kong Shen)
Re: Encrypting Predictable Files ([EMAIL PROTECTED])
Re: ith bit of an LFSR sequence? ("Douglas A. Gwyn")
Re: 1 to 4 byte hash function ("Joseph Ashwood")
Re: Phillo's alg is faster than index calculus ("Brian Wong")
Re: ith bit of an LFSR sequence? ("Douglas A. Gwyn")
Re: Some basic questions ([EMAIL PROTECTED])
Re: relative key strength private vs public key (Splaat23)
Re: Phillo's alg is faster than index calculus (Mok-Kong Shen)
Re: Phillo's alg is faster than index calculus ([EMAIL PROTECTED])
Re: use of AES?? help (Greggy)
Re: relative key strength private vs public key (DJohn37050)
Re: Rijndael's resistance to known plaintext attack ("Douglas A. Gwyn")
Re: Encrypting Predictable Files ("Douglas A. Gwyn")
Re: Pseudo Random Number Generator (Mok-Kong Shen)
Re: Encrypting Predictable Files ("Douglas A. Gwyn")
----------------------------------------------------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: relative key strength private vs public key
Date: Wed, 07 Feb 2001 20:57:47 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (DJohn37050) wrote:
> NIST in DSA-2 said that 1024 DSA keys are appropriate for 80 bit symmetric
> keys, 2048 DSA keys are appropriate for 112-bit TDES keys (TDES is considered
> to have an effective strength of 112 bits due to a meet in the middle attack).
> 3072 DSA keys for 128 bit AES low keys. up to 15760 DSA keys for 256 bit AES
> keys. DSA is considered to be slightly stronger than the same size RSA key, so
> the DSA key size can be used as an estimate for RSA. Note this is a TIME
> comparison.
And has no basis in REALITY. Assuming you have the required terabytes of
memory to mount the attack the listed key sizes are appropriate.
Tom
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Pseudo Random Number Generator
Date: Wed, 07 Feb 2001 22:15:05 +0100
Benjamin Goldberg wrote:
>
[snip]
> I would define it slightly differently... There must be at least two
> values with non-zero probability, and the GCD of all values and n must
> be one.
I don't yet comprehend what do you mean. Do you mean the
following for, say, n=7: PRNGA gives 2 with p=0.1 and 3
with p=0.9, PRNGB gives 2 with p=0.3 and 3 with p=0.7
and their sum mod 7 would be a uniform random variable
over [0, 6]? (That evidently can never be true.)
M. K. Shen
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Encrypting Predictable Files
Date: Wed, 07 Feb 2001 21:14:03 GMT
In article <[EMAIL PROTECTED]>,
Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] wrote:
> [snip]
> > A good "all or nothing transform" is scott16u or scott19u
>
> Do you have a proof of that?
>
> > in either
> > one a single bit change anywhere in the input file creates totally
> > different ouput files.
>
> This is not the only requirement for AONT. One of the requirements of
> AONT is that if one applies it to two identical files, one usually
gets
> two different files. For example, using OAEP as your AONT, two
> identical plaintexts will produce two identical transformed texts with
> probability 2^-128.
>
Well maybe thats your definations of an all or
nothing transform but not mine. I am as you well
knoww talking about a bijective 1-1 transfrom where
if one applies it to 2 identical files. They would
get the same result. However if one bit of one of the
files any where in the file was different. You would get
2 totally different files all the way through the file.
Sent via Deja.com
http://www.deja.com/
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: ith bit of an LFSR sequence?
Date: Wed, 7 Feb 2001 20:44:53 GMT
[EMAIL PROTECTED] wrote:
> Hmmm. I always wondered why the NSA likes LFSRs.
"liking" them could be done for any combination of at
least three reasons:
(a) they have simple, fast hardware implementations;
(b) their mathematical properties are well understood;
(c) they're easy to break.
"Everyone" knows (a) is true; (b) is indicated by the
literature, such as Golomb's book available from Aegean
Park Press; (c) might be a consequence of (b), and is
indicated by numerous published articles.
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: 1 to 4 byte hash function
Date: Wed, 7 Feb 2001 13:08:59 -0800
"Akita Bright-Holloway" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>(and im definatly gona snag a peak at what other people
> have done)
I'd recommend taking a look at www.cryptonessie.org you'll find several
different types of building block algorithms. Unfortunately I only see 1
cryptographic hash function there. For other hashes, I'd suggest looking at
Tiger, SHA-256, SHA-512, no other good ones some to mind offhand.
Joe
------------------------------
From: "Brian Wong" <[EMAIL PROTECTED]>
Subject: Re: Phillo's alg is faster than index calculus
Date: Wed, 7 Feb 2001 16:40:13 -0500
"Mok-Kong Shen" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
>
> [snip]
> case must normally always be addressed. To make an analogy
> with your example, consider the inversion of a (non-singular)
> n*n matrix. The cost of computation in general increases
> exponentially with n. But if I have a diagonal matrix
Inverting a matrix is O(n^3) naively.
> with all 1's on the diagonal, then I can give the inverse
> matrix to you for arbitrarily large n in zero time. Do you
> see my point?
>
> M. K. Shen
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: ith bit of an LFSR sequence?
Date: Wed, 7 Feb 2001 21:25:01 GMT
Benjamin Goldberg wrote:
> If we know x (or know n bits starting at i), and know y, and want to
> know i, what do we do? This is the second thing Bob asked about. THIS
> problem is exactly equal in difficulty to the discrete log problem.
This suggests the possibility of fast hardware DLP solvers...
------------------------------
From: [EMAIL PROTECTED]
Reply-To: [EMAIL PROTECTED]
Subject: Re: Some basic questions
Date: Wed, 07 Feb 2001 22:14:20 +0000
Geoff Blair wrote:
>
> OK. Im a newbie. With that said I will ask my questions and run for cover in
> case i get flamed for asking them in such a respected news group.
>
> 1. Can anyone point me to some source material about the very basics of
> cryptography?
> 2. I have been programing using several languages for years now and I
> was wondering about a code word I keep hearing about but have never see
> explained. What is XOR and what does it do?
> 3. What is the average key length for the best security systems online
> right now?
There is no reason to be flamed for asking questions. Answering a
question grossly incorrect is a far greater cause of flames, especially
when being demeaning to the question asked. Cryptography has no room for
mistakes.
sci.crypt FAQ
<URL:http://www.faqs.org/faqs/by-newsgroup/sci/sci.crypt.html>
it one starting place, although it has not updated in a long time
Other FAQs include: RSA Security's FAQ
<URL:http://www.rsasecurity.com/rsalabs/faq/>
and Cryptography A-to-Z from SSH Communications
<URL:http://www.ssh.fi/tech/crypto/>.
I strongly recommend _The Codebreakers_ by David Kahn. It is a
comprehensive history of cryptology, and if more people in sci.crypt
read it there would be less garbage posted to sci.crypt because a)
people make the same mistakes have been repeatedly made throughout
cryptology's long history, and b) people keep "rediscovering" weak
ciphers algorithms about twice a week.
Please read it, or at least one book about the history of cryptography
(_The Code Book_, or even any one of the dozen of decent WWII/ Engima
histories are alternatives to _the book_).
To get more details, it becomes largely influenced by your mathematical
skills and background.
_Decrypted Secrets_ by F L Bauer is a often recommended book. For the
math loving geek _Cryptography: Theory and Practice_ by D. Stinson, and
_A Course in Number Theory and Cryptography_ by N. Koblitz are two often
recommended starting points -- these are oriented to someone with a good
grasp of undergraduate level mathematics (number theory, abstract
algebra, statistics).
_Codes and Cryptography_ by Dominic Welsh is written for a course in
communication theory, good if you're an EE type. _An Introduction to
Cryptography_ by R. A. Mollin is written for an undergrad level
university course.
_Applied Cryptography_ by Schiener is not the be-all-end-all that some
make it out to be. It is very good reference, and very practical, but it
does not "get low-down and dirty" with a good understanding of the many
details in my opinion. _Handbook of Applied Cryptography_ by A.
Menezes, P. van Oorschot and S. Vanstone is available from the authors
at <URL:http://www.cacr.math.uwaterloo.ca/hac/> is another excellent
reference. Another book I suspect will become very popular and v. useful
for the practical types is _Security Engineering: A Guide to Building
Dependable Distributed Systems_ by R. Anderson and is due to be
published this month (February 2001).
So in summary:
1. Get _The Codebreakers_, read it, digest it
2. Flip through the download of _Handbook of Applied Cryptography_, to
help determine your mathematical level, and go from there.
3. get whatever suits your needs/desires
XOR is exclusive-or, a logical bit-wise operation.
Be wary of encryption which is largely dependent on XOR. For more
details see the Snake Oil FAQ
<URL:http://www.interhack.net/people/cmcurtin/snake-oil-faq.html>
To answer question 3 takes a lot of explaining. "It depends" is the
short answer. 64 to 128 bit today, is an answer with a lot of
understated assumptions.
56-bit DES was brute-forced in less than 24 hours by EFF DeepCrack
hardware and distributed.net in 1999.
<URL:http://www.distributed.net/des/> and
<URL:http://www.eff.org/pub/Privacy/Crypto/Crypto_misc/DESCracker/>
An idea of key lengths for symmetric ciphers is given in this 1996 paper
Minimal Key Lengths for Symmetric Ciphers to Provide Adequate Commercial
Security <URL:http://www.crypto.com/papers/keylength.txt>. There are
other articles and papers since, but this is a accessible start.
The recently selected AES (not yet a final standard) is designed to
operate in 3 sizes.
>From <URL:http://csrc.nist.gov/encryption/aes/>
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.
In comparison, DES keys are 56 bits long, which means there are
approximately 7.2 x 10^16 possible DES keys. Thus, there are on the
order of 10^21 times more AES 128-bit keys than DES 56-bit keys.
Algorithms like RSA, ECC, and DH, which are not symmetric ciphers rely
on different things to provide security. RSA is based on the difficulty
in factoring very large numbers, and Diffie-Hellman on the discrete
logarithm problem
<URL:http://www.rsasecurity.com/rsalabs/faq/3-6-1.html>. These are of
different sizes due to this being based on different problems. 512-bit
number has been factored in August 1999, this implies 512-bit RSA keys
are typically considered too weak.
<URL:http://www.rsasecurity.com/rsalabs/challenges/factoring/rsa155.html>
By the way, just in case I didn't make myself clear, read _The
Codebreakers_ by David Kahn. It's a big book, but you will know a lot
about cryptography if you read it.
------------------------------
From: Splaat23 <[EMAIL PROTECTED]>
Subject: Re: relative key strength private vs public key
Date: Wed, 07 Feb 2001 22:24:50 GMT
So at least you can use these numbers as worst-case approximations, and
work from there, depending on a tradeoff between risk and speed/size.
Of course, you can always describe your requirements exactly and do
some good research so get better approximations, but of course, that's
all these are. No one can really see the future, but we have to deal
with the future, so approximations and trends are all we have to work
with.
- Andrew
In article <95scs5$4im$[EMAIL PROTECTED]>,
Tom St Denis <[EMAIL PROTECTED]> wrote:
> In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] (DJohn37050) wrote:
> > NIST in DSA-2 said that 1024 DSA keys are appropriate for 80 bit
symmetric
> > keys, 2048 DSA keys are appropriate for 112-bit TDES keys (TDES is
considered
> > to have an effective strength of 112 bits due to a meet in the
middle attack).
> > 3072 DSA keys for 128 bit AES low keys. up to 15760 DSA keys for
256 bit AES
> > keys. DSA is considered to be slightly stronger than the same size
RSA key, so
> > the DSA key size can be used as an estimate for RSA. Note this is
a TIME
> > comparison.
>
> And has no basis in REALITY. Assuming you have the required
terabytes of
> memory to mount the attack the listed key sizes are appropriate.
>
> Tom
>
> Sent via Deja.com
> http://www.deja.com/
>
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Phillo's alg is faster than index calculus
Date: Wed, 07 Feb 2001 23:38:03 +0100
Brian Wong wrote:
>
> "Mok-Kong Shen" <[EMAIL PROTECTED]> wrote:
> >
> >
> > [snip]
>
> > case must normally always be addressed. To make an analogy
> > with your example, consider the inversion of a (non-singular)
> > n*n matrix. The cost of computation in general increases
> > exponentially with n. But if I have a diagonal matrix
>
> Inverting a matrix is O(n^3) naively.
You are right. I used a wrong term.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Phillo's alg is faster than index calculus
Date: Wed, 07 Feb 2001 22:34:25 GMT
If we have 2^k memory, we can do 2^k precomputations. Then we have 2^k
special cases. That surely will speed up our computation. That's how the
other cryptanalysis schemes work.
Everyone is arguing that this method is not practical for large n. Yeah
I know that. But index calculus is not practical either. So do you think
this scheme can or cannot be faster than index calculus? (In case anyone
is wondering, the implication of this question is that if it can, we
need to increase our key size by another notch.)
Nobody's up to the challenge so far. How disappointing.
Another point: I think this method creates a whole new class of trivial
cases that we should avoid. Just like Mersenne Primes should be avoided.
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Greggy <[EMAIL PROTECTED]>
Subject: Re: use of AES?? help
Date: Wed, 07 Feb 2001 22:34:59 GMT
In article <95narp$nhe$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Hello all,
> being new to Encryption and NOT being a
> specialized Cypher programmer (just someone in
> the real world) with the task of having to
> encrypt data on a server/database, I have the
> following questions that if someone could help or
> point me in the right direction, It would be
> greatly appreciated. Here is the scope of my
> problem.
>
> I have a working cypher program that is based on
> the new AES – “Rijndael” - (downloaded from
> Rijndael home page and verified with KAT’s- known-
> answer-tests) and I am trying to implement it
> into a working solution for in-house use to
> encrypt data that is stored on a server and/or a
> database. My first inclination was to wrap the
> original code into a DLL component that will
> handle the various error trapping, block length,
> padding and other issues. My process would be as
> follows a) first encrypt simple plain text that
> is sent in as a method and will reside within the
> server HD/database, then later b) to encrypt
> files (will also reside on same server as
> component) and lastly maybe to encrypt email or
> other data that will be sent via the internet. I
> will start in the phases listed above.
>
> My questions are as follows:
> Am I ok just using Symmetric keys and hiding this
> key in a file??? In the component itself???
> What is my weakest link here – the act of hiding
> the key or the component wrapper that I built?
>
> Am I off the mark here and/or does anyone have
> any more information that I could read up on to
> successfully implant such a project.
> Thanks in advance.
> Ody.
One weak link is the fact that you want to use DLLs to wrap the
cipher. A virus (if a virus is a threat to your server) can
programmaticaly place itself between the DLL and the code calling into
the DLL. The virus can thus see the plain text. This is not a DLL
issue, but a windows architecture issue. It is like Microsoft
engineers needed a way to insert between a DLL and the parent code and
thus left a door wide open. I suggest you use only static libraries.
--
I prefer the fourth amendment over a drug free society.
Did W declare the national emergency over yet and give us
back constitution rule? No? Why am I not surprised?
Sent via Deja.com
http://www.deja.com/
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Date: 07 Feb 2001 22:40:19 GMT
Subject: Re: relative key strength private vs public key
As I said, these numbers are from NIST, who gets to consult with NSA on these
matters. Duh!
Don Johnson
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Rijndael's resistance to known plaintext attack
Date: Wed, 7 Feb 2001 21:44:33 GMT
Splaat23 wrote:
> And even if the NSA can destroy our ciphers through some top secret
> attack, what should we do? We must simply hope and trust that the peer
> review of those ciphers we use is comprehensive. A cipher that is
> resistant to all known attacks will stand a good chance of holding up
> against specific attacks and unknown attacks. If nothing else, it has a
> better chance than proprietary or homemade siphers.
You're using "chance" as though you were talking about
probabilities of some inherently random event, whereas
actually you're talking about your subjective estimate
of likelihoods based on your current state of knowledge.
In which case, what logical justification is there for
claiming that resistance to known attacks means likely
resistance to unknown attacks? I agree that it is
rational to make decisions based on the best available
knowledge, but it is good practice to keep in mind that
that is what one is doing. Extrapolating from the
known to the unknown is "likely" to be misleading,
unless one uses guiding principles (such as math
theorems) that can be relied on in the unknown domain.
> Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
> > > If you only have a few blocks (unicity distance) of known plaintext,
> > > the only attack you can mount is brute force.
The above claim is not borne out in practice for other
systems, so it needs to be proven for this one (Rijndael).
Scott's point was that the problem is in principle
solvable; indeed we know an inefficient algorithm
that solves it. The serious questions are whether a
vastly more effective algorithm is possible or not,
and if so, whether one's adversaries might be able
to discover and apply it. It is clear that any
such algorithm was not reported during the AES
evaluation, which has some relevance for estimating
likelihood for the latter question but not for the
former.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Encrypting Predictable Files
Date: Wed, 7 Feb 2001 21:50:27 GMT
Richard Heathfield wrote:
> (Idle speculation: is Mr Szopa really just a cover identity for Doug
> Gwyn, so that he can take the mickey out of the whole group with
> carefree abandon? Ah, what a frabjous hack that would be...)
No, I don't see any need for such an element,
as there is plenty of amusement potential already.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Pseudo Random Number Generator
Date: Thu, 08 Feb 2001 00:03:38 +0100
Mok-Kong Shen wrote:
>
> Benjamin Goldberg wrote:
> >
> [snip]
> > I would define it slightly differently... There must be at least two
> > values with non-zero probability, and the GCD of all values and n must
> > be one.
>
> I don't yet comprehend what do you mean. Do you mean the
> following for, say, n=7: PRNGA gives 2 with p=0.1 and 3
> with p=0.9, PRNGB gives 2 with p=0.3 and 3 with p=0.7
> and their sum mod 7 would be a uniform random variable
> over [0, 6]? (That evidently can never be true.)
I see now what you mean. It suffices for all random variables
to take on at least one value that is relatively prime to n
in order to have their sum mod n approach a uniform random
variable in the limit.
M. K. Shen
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Encrypting Predictable Files
Date: Wed, 7 Feb 2001 22:14:40 GMT
[EMAIL PROTECTED] wrote:
> You would realize that good encryption hids the data with a key
> but that that key information should not be part of the encrypted file.
I think part of the problem here is that the terms "information"
and "containment" are being used very informally, so their
properties are subject to interpretation. Consider an N-bit
plaintext P and an N-bit key K, with the N-bit ciphertext produced
by simply C = P xor K . Does C "contain information about K"?
Note that if P and K are uniform random (and independent), C
contains N bits of entropy, which is not enough to reasonably say
that it "contains" all the entropy of P *and* all the entropy of K.
("Containing" seems to imply some sort of additive property.)
So you have to either give up the connection between information
and entropy or else say that the "contained" information cannot be
partitioned into that belonging to P and that belonging to K.
(In a more complete treatment, one would deal with the fact that
information is contextual, but it doesn't change the main result.)
So in a sense Scott is right -- good encryption does not *add* the
key information into the ciphertext; however, it does *mix* the
key information with the plaintext information to produce the
ciphertext information. (The uses to which the ciphertext
information can be put, such as to recover the plaintext or to
recover the key, depend on context, such as what other information
one is assumed to possess.)
I wish you guys would drop the insults and stick to the technical
issues.
------------------------------
** 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
******************************
