Cryptography-Digest Digest #416, Volume #13 Wed, 3 Jan 01 13:13:01 EST
Contents:
Birthday attack explanation... ([EMAIL PROTECTED])
Re: Audio-CD steganography? ([EMAIL PROTECTED])
Differential Analysis (Benjamin Goldberg)
Re: AES in optimized x86 assembler? (Paul Crowley)
Re: Generating 128bit key from user password (Paul Crowley)
Re: Birthday attack explanation... (thierry nivon)
Re: Very Simple Gift Certificate Scheme (Shawn Willden)
Baltimore KeyTools lite java api ([EMAIL PROTECTED])
[Q] Question about encrypted private keys of PGP (TGOS)
Re: "Content Protection for Recordable Media" (Pallex)
Re: Audio-CD steganography? (Mok-Kong Shen)
Re: unique codes (Mok-Kong Shen)
Re: Genomes (Mok-Kong Shen)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Birthday attack explanation...
Date: Wed, 03 Jan 2001 15:00:34 GMT
Hello,
I have read on RSA Labs FAQ (http://www.rsalabs.com/faq/2-4-6.html)
concerning birthday attack on hash functions that :
if I generate 2^(n/2) hashes of an innocuous messsage (with minor
changes) Bob is likely to sign
and 2^(n/2) hashes of real message to be signed (in which I can make
Bob say whatever I like...)
where n is the length to the message digest
there is over fifty percent of chances I get once the same hash for one
innocuous message and one real message.
=> If we apply that to SHA-1, length of message digest is 20 bytes =
160 bits. That means I only have to compute 2^80 innocuous messages +
2^80 real messages ?
I'm surprised 2^80 isn't that big... (unless computing a hash is very
long ?). Isn't that an important security threat ? I must have missed
something...
Thanks for any explanation on the subject,
Axelle.
Sent via Deja.com
http://www.deja.com/
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Audio-CD steganography?
Date: Wed, 03 Jan 2001 15:21:07 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> Graphical files allow hiding of bits through appropriate
> modification of pixels. Wouldn't it be possible to do
> analogous modifications to audio data? If yes, how good
> is that? Thanks.
I would hazard a guess that it's an even more fertile field to plow,
since on average a digital audio clip has many more samples than an
image has pixels. As a naive approach, simply replacing an occasional
sample will most likely go unnoticed by the casual listener, since the
pop or hiss introduced will be well under a millisecond.
For anything that can be expressed as a waveform, you might be able to
compose the hidden message with the original recording. I'm not sure
how practical that is, since you'd have to avoid audible differences,
but I suspect it's possible.
As far as cd's go though, I'm not sure that's a particuarly practical
place to conceal messages, given the amount of work in creating one. A
cd-r, for example, won't be too convincing to a non-casual
observeror. On the other hand, an actual replicated platter is quite a
bit more expensive.
If you're playing the "unlimited budget" game, however, it's possible
to hide your message on another layer, which won't even be readable by
normal cd players. Either that, or use a different frequency laser to
read smaller pits in between the normal tracks.
--
Matt Gauthier <[EMAIL PROTECTED]>
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Differential Analysis
Date: Wed, 03 Jan 2001 15:57:31 GMT
Could anyone point me to an _online_ resource which describes exactly
how to do differential analysis? Most of the stuff I've found is much
to vague to go from their description to something resembling an attack.
The reason I'm asking this is I want to analyse my "hypercrypt" cipher,
and I want to know how many inner rounds and how many outer rounds are
needed to make it secure against differential analysis. I *think* that
if enough rounds are used in the mixing primitive (a 16 bit fiestel with
the AES sbox), only one or two outer rounds are needed, but I'm not
sure.
--
Power interrupts. Uninterruptable power interrupts absolutely.
[Stolen from Vincent Seifert's web page]
------------------------------
From: Paul Crowley <[EMAIL PROTECTED]>
Subject: Re: AES in optimized x86 assembler?
Date: Wed, 03 Jan 2001 13:02:52 GMT
graywane wrote:
> In article <[EMAIL PROTECTED]>, Marc wrote:
> > Do already optimized x86 Assembler versions of AES exist as
> > source code?
>
> Premature optimization is the root of all evil.
Off hand, I can think of no better candidate for assembly hacking than
AES on the x86.
* Crypto routines are great candidates for assembly implementation:
they're small, they perform an extremely well defined function with a
simple interface, and under some circumstances they're an application
bottleneck.
* x86 is not a compiler-friendly IA, so hand-hacked assembly by an
expert still does considerably better than compiler-generated code.
Especially if your compiler is GCC; x86 optimisation is not GCC's strong
suit. See http://www.goof.com/pcg/
* I for one hope to see AES universally adopted as the default crypto
algorithm. x86 is the most widely-used IA inthe world. It could be one
of the most popular bits of assembly ever.
Admittedly, Rijndael is a very compiler-friendly algorithm, so it might
benefit from assembly coding less than most tight loops. Nevertheless,
I'm very surprised that several blazing x86-asm implementations of this
algorithm aren't already duelling for speed supremacy; the only such
implementation listed on http://www.rijndael.com/implementations.html
uses only 8086 instructions and is optimized for size, not speed.
Come on, you x86 speed demons, here's a challenge worth leaping to! How
much better than gcc -O3 can you do?
--
__
\/ o\ [EMAIL PROTECTED]
/\__/ http://www.cluefactory.org.uk/paul/
------------------------------
From: Paul Crowley <[EMAIL PROTECTED]>
Subject: Re: Generating 128bit key from user password
Date: Wed, 03 Jan 2001 13:29:29 GMT
Marc wrote:
>
> In a code space critical application I want to generate a
> 128bit key from a user password/passphrase. If possible, I
> want to avoid using MD5 or a similar algorithm for that
> purpose, and instead use a block cipher (which is already
> there). The main goal is to discourage on-the-fly dictionary
> attacks.
In that case, you want to construct a hash function from a block cipher.
There are many constructions to do this: Miyaguchi-Preneel (and others)
produces a hash the same size as the block, while Tandem Davis-Meyer and
Abreast Davis-Meyer (to name two I know) produce a hash twice the size
of the block. I think Applied Cryptography covers these methods;
there's also some information and references in Chapter 9 of the
Handbook of Applied Cryptography:
http://www.cacr.math.uwaterloo.ca/hac/
To turn a passphrase into a key using a hash function, follow the
instructions in
http://www.counterpane.com/low-entropy.html
This will avoid the use of homebrew constructions, which are a Bad Idea.
hope this helps,
--
__
\/ o\ [EMAIL PROTECTED]
/\__/ http://www.cluefactory.org.uk/paul/
------------------------------
From: thierry nivon <[EMAIL PROTECTED]>
Subject: Re: Birthday attack explanation...
Date: Wed, 03 Jan 2001 17:53:17 +0100
try to make the calcul
2^80 is about 10^24 !
you have to stock about 10^24 messages and hash 10^24 messages
[EMAIL PROTECTED] wrote:
> Hello,
>
> I have read on RSA Labs FAQ (http://www.rsalabs.com/faq/2-4-6.html)
> concerning birthday attack on hash functions that :
> if I generate 2^(n/2) hashes of an innocuous messsage (with minor
> changes) Bob is likely to sign
> and 2^(n/2) hashes of real message to be signed (in which I can make
> Bob say whatever I like...)
>
> where n is the length to the message digest
>
> there is over fifty percent of chances I get once the same hash for one
> innocuous message and one real message.
>
> => If we apply that to SHA-1, length of message digest is 20 bytes =
> 160 bits. That means I only have to compute 2^80 innocuous messages +
> 2^80 real messages ?
>
> I'm surprised 2^80 isn't that big... (unless computing a hash is very
> long ?). Isn't that an important security threat ? I must have missed
> something...
>
> Thanks for any explanation on the subject,
> Axelle.
>
> Sent via Deja.com
> http://www.deja.com/
------------------------------
From: Shawn Willden <[EMAIL PROTECTED]>
Subject: Re: Very Simple Gift Certificate Scheme
Date: Tue, 2 Jan 2001 23:23:25 -0700
Tom St Denis wrote:
> http://www.geocities.com/tomstdenis/files/gcert.ps.gz
It would be a good idea to think hard about what the properties of these
simple "certificates" are in abstract terms, to help explain when they're
appropriate. For a first stab, these digital tokens are:
1. Issued and verified by the same party
2. Resistant to forgery
3. Vulnerable to replay
4. Simple to generate and verify
5. Don't require an interactive protocol for either issuance or redemption
6. Variable sized (something you neglected to mention)
FWIW, the most common approach I have seen in web applications to
implementing something like this (for cookies), is to encrypt a suitable
chunk of data (often just just some zeros concatenated to a serial number)
using a symmetric block cipher (i.e. DES). A hash-based approach has the
advantage that it allows more flexibility in terms of the size of a
token whereas a block cipher-based approach requires that the
token be at least one block in size* (ciphertext-stealing can be used to
eliminate the requirement that it be a multiple of the block size). The
block cipher-based approach has the advantage that other useful bits of
information can be embedded in the token (account numbers and such) which
can often be used to eliminate some extra database lookups.
Two other things I noted in your paper that seem like errors:
(1) You state that a base-64 encoded token would be approximately 43
characters in length. Assuming you're talking about a 128-bit serial
number with a 160-bit hash for a 288-bit token, that would be 48 characters.
(2) You also state that with a 128-bit serial number, the probability of a
"valid" fake token being generated is 2^-32. Given your approach, there's
no reason why that shouldn't be 2^-160, AFAICS. Unless I'm missing
something, you appear to be assuming that if you're using a 128-bit serial
number with a 160-bit hash, you can only use a 32-bit key, but there's no
reason to limit the size of the key. Just hash the 128-bit serial number
with a 160-bit key and, assuming the key is good, you'll have close to 160
bits of entropy in H (of which you can use as much or as little as you
like, giving the flexibility of token size).
* Of course, you could use a block cipher as a keyed hash and then you
could get the same size flexibility as with the hash as you describe it.
Shawn.
------------------------------
From: [EMAIL PROTECTED]
Subject: Baltimore KeyTools lite java api
Date: Wed, 03 Jan 2001 16:57:15 GMT
Hi,
I am having trouble packaging a java encryption class as a Microsoft
COM object.
When I use Baltimore KeyTools lite (free) I can package up a dll which
can be successfully called from a visual basic test harness with both
early and late binding. However when I register the dll under mtx I
get a ClassNotFoundException at the line
Security.insertProviderAt(JCRYPTO(),1);
when the method is called from asp
If the application is recompiled against Baltimore JCRYPTO v4.0 API
(3000 dollars)
I can call it successfully from asp.
Any ideas ? I looks like they are limiting their 'free' product to
me ...
Simon.
--
Take the bird out to reply.
email: simonepstein@hot[chick]mail.com
Sent via Deja.com
http://www.deja.com/
------------------------------
From: TGOS <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp,comp.security.pgp.discuss,comp.security.pgp.tech
Subject: [Q] Question about encrypted private keys of PGP
Date: 3 Jan 2001 11:29:06 -0600
[The following post is a xpost, a Followup-To has been set. If you don't reply
to the group in the Followup-To line and also don't keep the xpost, your reply
may not get read by the questioner. Of course you are free to send a CC via
mail in that case.]
As you can guess by the groups in the header, I have a question regarding PGP,
more precisely regarding encryption used by PGP.
The private keys of PGP are stored encrypted on HD, even if an attacker would
have access to the key-files, he wouldn't be able to use the key, unless he
knows the password.
Now let's assume I have such a key-file, but I don't know the password. The
only way to get it would be brute-force, not quite effective. Fortunately I
have some knowledge about the password.
I know:
- The password is longer than 6 chars. I don't know how long it is (7, 8, 9 ...
100), but since I know that I can't be a very long one, the likeliness is
decreases for increasing numbers. Working with likeliness is always a good way
to avoid that you have to try all possible keys, isn't it?
- Even better, I do not only know that it's longer than 6 chars, I even know
the first 6 chars. This makes it also very likely to predict the next char(s),
as it looks like only [A-Z][a-z][0-9] are used, so I can most likely limit the
search to that range.
My question is:
Is there any way to predict how many chars of the password must be missing
using the knowledge of above? If it would be only 1, it can probably be found
within a few seconds (max. 256 possibilities, and I can exclude more than 127
of those). I don't know how long it will take for 2 or 3 chars, but knowing how
long the password is, makes it easy to predict how long it would take.
Being able to predict the time makes it easy to decide if it's even worth the
effort. If it would take 2 weeks, it's maybe worth a try, if it takes 2 years,
forget it.
I admit that I don't know which encryption standard PGP uses to save private
keys and even if I would know that, I doubt that it would help me, I'm no
expert on this topic.
Despite finding out how long the pass is, it would also be interesting if the 6
known chars can be used in any way to make assumptions about the x missing
chars (regardless if their number is known or not).
In case it's neither possible to find out how many chars are missing, nor to
say anything about the missing chars, it wouldn't be helpful at all to know
those 6 chars, right? It wouldn't only help as it means that I don't have to
try the first 2^48 possibilities and that I can make assumptions about the
missing chars by looking at the already existing ones, but despite that, the
key is still quite safe (especially in the unlikely case that the password is
12 or more chars long).
Any information on that topic would be appreciated.
Of course links to pages regarding this topic or Message-IDs for Deja searches
will also be helpful.
--
TGOS
------------------------------
From: Pallex <[EMAIL PROTECTED]>
Subject: Re: "Content Protection for Recordable Media"
Date: Wed, 03 Jan 2001 17:32:16 GMT
>compliant devices will look for this watermark and deal with the media
>appropriately (in some cases refusing to play it) "
"Hello, i`d like a compliant device please...one that doesnt let me
play my mp3`s. Oh, and one of those special hard drives, so i cant
read and write my own data freely."
I`m sure all these plans make sense to somebody! Perhaps they are
living in a parallel universe, when all the time, money and effort
spent, both by developers and users, on copy-protecting software hasnt
been a complete and utter waste of time.
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Audio-CD steganography?
Date: Wed, 03 Jan 2001 18:58:38 +0100
[EMAIL PROTECTED] wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> > Graphical files allow hiding of bits through appropriate
> > modification of pixels. Wouldn't it be possible to do
> > analogous modifications to audio data? If yes, how good
> > is that? Thanks.
>
> I would hazard a guess that it's an even more fertile field to plow,
> since on average a digital audio clip has many more samples than an
> image has pixels. As a naive approach, simply replacing an occasional
> sample will most likely go unnoticed by the casual listener, since the
> pop or hiss introduced will be well under a millisecond.
>
> For anything that can be expressed as a waveform, you might be able to
> compose the hidden message with the original recording. I'm not sure
> how practical that is, since you'd have to avoid audible differences,
> but I suspect it's possible.
I have no knowledge. But if the difference were a nuance
of accent, then it could easily pass scrutiny, I believe.
(I read recently an article claiming to have found a
variation of accent in the Queen's English through
comparing her different Christmas speeches over time.)
> As far as cd's go though, I'm not sure that's a particuarly practical
> place to conceal messages, given the amount of work in creating one. A
> cd-r, for example, won't be too convincing to a non-casual
> observeror. On the other hand, an actual replicated platter is quite a
> bit more expensive.
>
> If you're playing the "unlimited budget" game, however, it's possible
> to hide your message on another layer, which won't even be readable by
> normal cd players. Either that, or use a different frequency laser to
> read smaller pits in between the normal tracks.
If the steganographical technique were simple enough to
implement, then I guess that it could even be employed
in normal telephone communications.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: unique codes
Date: Wed, 03 Jan 2001 18:58:47 +0100
Tom St Denis wrote:
>
> [EMAIL PROTECTED] (Eric Mosley) wrote:
> >
> > I recentlt received a promotional gift certificate from Amazon. It was
> > designated by a unique code:
> > CLAIM CODE : XM82-VJY26W-H2LCNQ
> > Now, I need to generate unique codes like that! Does anybody know of
> an
> > appropriate algorithm or software library that could be used to
> generate
> > codes like that. I think the key thing here is that you have to be
> > unlikely to be able to guess somebody elses/another code..
>
> Simple do this
>
> 1. Take a secret piece of data
> 2. Take a serial number
> 3. Output the hash of the data and serial number, output the serial
> number
>
> Then attackers cannot make up other valid serial number/hashes pairs.
If the code contains the serial number as a subsequence,
then it is certainly uniquue. But I suppose that part
of the requirements of the original poster is not to let
the code leak any information useful to a third party.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Genomes
Date: Wed, 03 Jan 2001 18:59:04 +0100
"Trevor L. Jackson, III" wrote:
>
> Mok-Kong Shen wrote:
>
> > Does anyone happen to know the statistical properties of the
> > genome sequences in general? Are they sufficiently 'random'?
> >
> > BTW, since the code is base 4, one can use the same to readily
> > transcribe any given binary sequences. This could have some
> > steganographical benefit, I suppose. For a paragraph that is
> > gibberish easily gives rise to suspicion of crypto, while the
> > same in the alphabet AGCT is presumably difficult to
> > distinguish from the result of a genetic research, if
> > appropriately enveloped. One could perhaps also hide information
> > in genuine genome sequences through modifications analogous to
> > what is done with graphical files.
> This may become less useful in the near future. If a distinguisher is
> found for valid (i.e., natural) introns then it becomes hard to hide
> random information as if it were an intron. Such a distinguisher may be
> feasible based on the fact that most of the genetic code for mammals is
> shared with all multi-cellular organisms. I suspect the introns would
> be shared too.
I have no knowledge. But from what I read in a book it
seems that introns vary comparatively significantly among
related genomes. So if a sequence is claimed to be
from an yet unstudied gene, it would be difficult to
detect the fraud, I guess.
M. K. Shen
------------------------------
** 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
******************************
