Cryptography-Digest Digest #878, Volume #10 Mon, 10 Jan 00 15:13:01 EST
Contents:
Single Prime Cipher (Tom St Denis)
Re: "1:1 adaptive huffman compression" doesn't work (Tim Tyler)
Re: Little "o" in "Big-O" notation ("r.e.s.")
Re: Questions about message digest functions ("Matt Timmermans")
Anyone give any pointers? ("Derek")
Re: compression & encryption (Tim Tyler)
Re: Intel 810 chipset Random Number Generator (Scott Nelson)
Re: "1:1 adaptive huffman compression" doesn't work (Mok-Kong Shen)
Re: "1:1 adaptive huffman compression" doesn't work (Mok-Kong Shen)
Re: Intel 810 chipset Random Number Generator (Scott Nelson)
Re: Example C programs to encrypt/decrypt password (Jerry Coffin)
----------------------------------------------------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Single Prime Cipher
Date: Mon, 10 Jan 2000 18:00:35 GMT
So about the P-H cipher (single prime). How does the attack work?
Last I understood you need an input for f(x) = x^e mod p, where x>p,
but if coded properly all inputs would be taken modulo p first. I
would use this cipher in CBC mode for example and do that.
I think I just mis-understood it...
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: "1:1 adaptive huffman compression" doesn't work
Reply-To: [EMAIL PROTECTED]
Date: Mon, 10 Jan 2000 18:04:03 GMT
Daniel Vogelheim <[EMAIL PROTECTED]> wrote:
: after following some recent discussion in this newsgroup, I looked at
: the "1:1 adaptive huffman compression" as described on page
: http://members.xoom.com/ecil/dspaper.htm. It describes 5 rules about
: how to cut off the last bits of the message in order to achieve
: byte-sized output. I think this idea is fundamentally flawed, as
: simply discarding information should make reconstruction impossible in
: general. This means the uncompressor will fail to reconstruct the
: original file in some of the cut-off cases. I.e., it just won't work!
This is completely wrong - no information need be lost, /despite/ the
"apparent" truncation.
: Toying with one of the provided implementations for a few minutes
: supported this (http://members.xoom.com/ecil/ah2.zip, h2com.exe
: version 19990825, h2unc.exe version 19990922). One can construct
: multiple files that get "compressed" to the same output file. One such
: file is included in this message below (uuencoded).
If someone else doesn't beat me to it I'll look at this and report back.
If there's a bug in Scott's compressor I've not yet heard about it, and
I'm sure he would be interested to learn about it. However the idea of a
1-1 Huffman compressor is definitely not itself conceptually flawed.
Such a 1-1 compressor will almost /inevitably/ involve truncation of
trailing zeros, or some such. These can be losslessly reconstructed by
the Huffman decompressor, however.
One idea behind such a scheme is essentially that if the EOF occurs while
the decompressor is in the middle of a symbol, it *knows* that this can
only happen if the decompressor chopped of a tail of zeros. This tail of
zeros can be unambiguously reconstructed *provided* the file does not end
with any all-zero Huffman symbols - and this case can be avoided fairly
simply.
Consequently, no information need get "lost" when a tail of zeros gets
chopped off.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
This tagline invokes Satan, Lord of Evil.
------------------------------
From: "r.e.s." <[EMAIL PROTECTED]>
Subject: Re: Little "o" in "Big-O" notation
Date: Mon, 10 Jan 2000 10:28:57 -0800
"Bob Silverman" <[EMAIL PROTECTED]> wrote ...
: "Scott Fluhrer" <[EMAIL PROTECTED]> wrote:
: >
: > o(f(x)) = g(x) is true iff:
: >
: > lim f(x) / g(x) = 0
: > x->oo
:
: TWO corrections.
:
: (1) You have the fraction reversed. It should be g(x)/f(x).
: (2) It should be |g(x)/f(x)|.
:
First: What's the point of your (2)?
Second: The proper correction was posted two days ago.
One could also check
http://mathworld.wolfram.com/AsymptoticNotation.html
--
r.e.s.
[EMAIL PROTECTED]
------------------------------
From: "Matt Timmermans" <[EMAIL PROTECTED]>
Subject: Re: Questions about message digest functions
Date: Mon, 10 Jan 2000 13:16:20 -0500
Scott Fluhrer wrote in message <856ao0$uvv$[EMAIL PROTECTED]>...
>Doing modular exponentions can be shown to be a permutation without giving
>away any secret material. That is, you can find particular values of g and
p
>such that:
>
> f(x) = (g**x) mod p
>
>can be demonstrated to be a permutation from (1..p-1) to (1..p-1), without
>there being any known way to compute the inverse in a reasonable period of
>time.
Oops. Right -- there is that one, of course.
------------------------------
From: "Derek" <[EMAIL PROTECTED]>
Subject: Anyone give any pointers?
Date: Mon, 10 Jan 2000 13:52:51 -0500
I'm trying to determine how a file is encrypted... I know the file is
stored as 256-byte records using sequential access. I also know the file is
enrypted using XORs on a per-byte basis, and each byte of the key has only
one bit set. Some files are encrypted while others are not, so I know the
underlying file format. I also know that the keys are the same at the same
byte position for every encrypted file -- but so far, I can't determine that
any it repeats anywhere, so it sounds like some sort of a randomly generated
key based the on record number or byte position. But I can't seem to make a
connection in the pattern -- how they're coming up with these key bytes.
The folks who engineered this file format are well-known for taking the
quickest and easiest route to implementation -- but the fact that they only
XOR one bit out of every byte confuses me. (It would seem easier to just
XOR the random number 0-255). I'm a complete amatuer at cryptography, but I
was hoping this would ring a bell as something simple that's well-known,
because if they treated this like everything else they do, they certainly
wouldn't have spent much time coming up with something very strong.
Thanks for any input you could provide.
Derek
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: compression & encryption
Reply-To: [EMAIL PROTECTED]
Date: Mon, 10 Jan 2000 18:56:33 GMT
Kenneth Almquist <[EMAIL PROTECTED]> wrote:
: Kenneth Almquist <[EMAIL PROTECTED]> wrote:
:> Tim Tyler <[EMAIL PROTECTED]> wrote:
:>: Compressing using a nonbijective algorithm and then encrypting twice
:>: may be faster than compressing using a bijective algorithm and then
:>: compressing once.
:>
:> Multiple encryption with independent algorithms and bijective
:> compression produce different types of security benefit.
: The security benefit in both cases is that the attacker has less
: information about the input to the encryption algorithm. (In the
: case of double encryption, I am referring to the input to the
: second encryption.)
This is a similarity in security benefits. Obviously there are
differences as well, and it was those to which I was referring
As an example of such a difference, in once case the attacker has more
cyphertext. If he has a known-plaintext attack that required N byes and
has a complete known plaintext to hand, this will have different
consequences in the two cases.
:>: That is because some of the compression algorithms
:>: which provide the best combination of speed and compression ratio
:>: (such as the one used by gzip) are not bijective.
:>
:> Bijective compression has only just been invented. The current
:> situation /should/ eventually reverse - since making a compression
:> system bijective demonstrably makes optimal use of the range of the
:> compressor.
: The algorithms with the best compression ratios are non-bijective only
: because of redundancies between the contents of the compressor output
: and the length of the compressor output.
Really? This is true of one technique of arithmetic/Huffman ending,
however, it is far from clear that this applies to other schemes.
Is it your claim that "arithmetic/Huffman" schemes are always those with
the best compression ratios?
: Since the length of the compressor output can be represented in log_2(N)
: bits, this redundancy wastes at *most* log_2(N) bits.
This seems true only of "arithmetic/Huffman" schemes. It is not clear
that these are "always the best".
:>: I believe that except in special circumstances, it is a mistake to
:>: assume that an opponent will not be able to mount a known plaintext
:>: attack. [...]
:>
:> Well yes - when analysing security, consider worst-case scenarios.
:>
:>: For this reason, I believe that the apparent improvement
:>: in security offered by bijective compression is an illusion.
:> There is no sign of logical argument, though. Compression reduces
:> the effectiveness of partial known plaintexts. It makes little
:> difference to *complete* known plaintexts. However, the former
:> are very common. Defending against them is likely to be genuinely
:> worthwhile, if you do not know for certain what attackers can do
:> with any known plaintext you give them.
: This is true of all types of compression.
Well, actually not. For some (often poor) types of compression, a partial
known plaintext gets compressed to another partial known plaintext.
Only if the compression has diffusion, or is adaptive, and is applied in
both directions do all known-partial plaintexts get scrabbled.
: I was addressing the question of whether bijective compression offers more security
:than
: non-bijective compression.
Your argment started with:
``I believe that except in special circumstances, it is a mistake to
assume that an opponent will not be able to mount a known plaintext
attack.''
Compression makes no difference to such attacks, it is true. However,
it can make a difference to "*partial* known plaintext" attacks and these
are probably much more common.
Because you can't use a technique to defend against a rare attack, that's
no reason to conclude that it's not worth using it to defend against a
common one.
:>: If your encryption algorithm is vulnerable to a known plaintext
:>: attack, then the chances are that a determined attacker will obtain
:>: a known plaintext an break your cipher, so it is not likely to matter
:>: whether you use bijective encryption.
:>
:> A known plaintext breaks a message key, not a cypher. If the attacker
:> faces a subsequent message, with a partial known plaintext, certain
:> types of compression can make a *big* difference to the attacker's
:> ability to exploit this.
: Here you appear to be assuming that each message is encrypted with a
: different key [...]
Yes. This seems generally sensible and is rather common.
[snip key distribution issues].
: To return to your point: I agree that the compression algorithm
: does make a difference. I assume by partial plaintext you mean that
: the attacker knows a section of the plaintext, but not what comes
: before or after it.
Yes.
: Scott's web site describes a bijective compression
: algorithm which uses a predefined mapping of strings to symbols.
Not AFAIK. You're probably thinking of *my* web site at
http://www.alife.co.uk/securecompress/ ?
: If this is the compression algorithm used, then the attacker with a
: known [partial] plaintext attack [can still succeed]
Yes. Scott's scheme is adaptive, though.
He recommedns applying an adpative compressor once in both directions
through the file.
My 1-1 compression idea presented on the pages above - if useful at all -
would probably be used as a preprocessor for Scott's scheme, while there
is no other static dictionary-based 1-1 compressor available.
: Switching to a different compression algorithm--an adaptive algorithm
: which alters its compression tables based on previous input--would
: make this type of attack much harder.
[snip adaptive compression]
[snip super-encryption method of destroying known-plaintext attacks]
: I use Square in the above construct because it's fast compared to
: compression algorithms or compared to more heavily analyzed encryption
: algorithms such as triple-DES or IDEA. So for a relatively small
: increase in processing time, you can get diffusion via a published
: algorithm which has been studied by professional cryptographers,
: rather than relying on the diffusion provided by a compression algorithm
: whose cryptographic properties were probably not even investigated by
: the original designers.
I agree that compression is not an ideal way of applying diffusion.
Personally, I think using any orthodox block-chaining method is
a sub-standard method of getting good diffusion. The onlt reason I can
think of for using such methods is that they are fast on serial hardware.
As I'm /mainly/ intereseted in heavily parallel implementations, this
doesn't make that much difference to me.
It is true that the "diffusion" you describe is effective against the
attack we have been discussing so far.
However, I think there are good reasons for applying diffusion that moves
the information necessary to recover the plaintext around in the file.
A CFB chaining mode does not appear to do this.
:>: Sure, it's *possible* for bijective compression to stop an attack on
:>: a cryptosystem, just as it's possible that prefixing the encrypted text
:>: with an obscene message will stop an attacker with delicate sensibilities.
:>: My point is that "possible" is not the same as "probable."
:>
:> Unfortunately, you present no clear argument about the relative costs.
:>
:> Yes, you should consider the expenditure on relevant components of
:> your system before deploying it. Compression is a good idea before
:> encryption for so many reasons, that it is quite likely you will be
:> employing it in some form anyway - the bijective compression enthusiasts
:> ask only that it be done properly.
: I mentioned the algorithm used by gzip, which (at least a few years
: ago when I last looked at compression algorithms) was very attractive
: in terms of throughput vs. compression ratio. It is not bijective,
: and is not readily modified to make it bijective. If you eliminate it
: from consideration for that reason, then you are left with alternatives
: which compress less effectively, are significantly slower, or both.
: Now consider a user who is short on disk space and compresses his
: files using (what else?) gzip, and later transfers one of these files
: to another system. The file transfer program may use bijective
: compression, but the file has already been compressed by a non-
: bijective compression algorithm, introducing information into the file
: that could help an attacker.
This is a problem that will remain around while non 1-1 compressors are
around.
As you go on to discuss, if every message is known to contain such
a "poorly compressed" file, this can introduce undesirable
known-plaintext into every message.
You discuss the problems involved and conclude:
: This should at least begin to point to the costs involved in ensuring
: that compression is "done properly" in a system when the system
: designer doesn't have control over the data to be transmitted.
*Sometimes* costs will be high.
However, for other applications, your objection is rather irrelevant.
For email messages, with no attachments, for example, your objection has
no force at all.
Also if poorly-compressed files are only sent *sometimes*, this is
still better than using the same problematical compression program as
part of your encryption program - since this introduces the same problem
with *every* message sent.
[much snipping]
: Second, compression makes the remaining regularities difficult to use.
[...]
: Whether the second increases security depends on whether the remaining
: regularities are actually obscured effectively, and I think it is hard
: to be confident that that is the case because compression algorithms
: are not designed to be cryptographicly secure, and have not been
: subject to the sort of scrutiny by crytographers that published cyphers
: have.
Yes, yes, yes - this is very true. Compression does not normally make
the remaining regularities difficult to use.
This does not even appear to have been much of a design gaol, at least
before 1-1 compression arrived. 1-1 compression was explicitly designed
to remove one type of "remaining regularity" - in the belief that
attackers may be able to exploit it.
: Furthermore, it is hard to even specify what it means for a
: compression algorithm to obscure regularities in a cryptographicly
: secure manner, since any compression can be efficiently reversed.
Well, you /could/ - in principle - use "keyed" compression - compression
which has been combined and "intertwined" with encryption.
However nearly everyone agrees that the simplicity and modularity involved
in keeping compression and encryption separate is very desirable.
: In contrast, block encryption algorithms are expressly designed to
: (among other things) obscure regularity. Thus I am much more willing
: to trust a suitably chosen block encryption algorithm to obscure all
: regularities, than I am to willing to count on a compression algorithm
: to either remove enough regularity or to obscure the regularity that
: it does not remove.
This is a good reason for super-encyphering. It may /even/ be a good
reason for regarding super-encyphering to be superior to compression,
at least in some respects. However, to have its full security benefits,
super-encypherment can involve an increase in the size of the key.
Note that encyphering disguises - but does not *remove* - regularity.
By contrast, compression actually removes some of the regularity
completely. This is better than just disguising it. It does this
without increasing the size of the key.
Of couse you should disguise any remaining regularities in the compressed
file *as well* - but that's what the subsequent encryption is for.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
Taxes are not levied for the benefit of the taxed.
------------------------------
From: [EMAIL PROTECTED] (Scott Nelson)
Subject: Re: Intel 810 chipset Random Number Generator
Reply-To: [EMAIL PROTECTED]
Date: Mon, 10 Jan 2000 19:17:19 GMT
On 7 Jan 2000 [EMAIL PROTECTED] (Bradley Yearwood) wrote:
>One interesting observation is that the device requires a variable
>amount of time to generate a new random byte. Availability of a new
>value is indicated by a status bit. They recommend a timeout of 4.5ms
>in polling this status, which appears to indicate a worst-case rate of
>random byte production of around 222 bytes/sec.
>
Actually, the worst case is infinite,
but the _average_ is claimed to be 75Kbits per second.
The odds against having to wait 4.5ms are extreme,
thus the recommendation that if you have to wait longer
than that, you should give up and assume there's a problem.
Scott Nelson <[EMAIL PROTECTED]>
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: "1:1 adaptive huffman compression" doesn't work
Date: Mon, 10 Jan 2000 20:20:31 +0100
Tim Tyler wrote:
>
> One idea behind such a scheme is essentially that if the EOF occurs while
> the decompressor is in the middle of a symbol, it *knows* that this can
> only happen if the decompressor chopped of a tail of zeros. This tail of
> zeros can be unambiguously reconstructed *provided* the file does not end
> with any all-zero Huffman symbols - and this case can be avoided fairly
> simply.
Excuse me, if I am arguing based on wrong knowledge (I haven't followed
the stuff for quite a while and perhaps have forgotten a lot). What
if the analyst decrypts with a wrong key which produces a file that
has at the end a sufficiently long sequence of zeros?
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: "1:1 adaptive huffman compression" doesn't work
Date: Mon, 10 Jan 2000 20:20:43 +0100
John Savard schrieb:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote, in part:
> >John Savard wrote:
>
> >> However, it is possible, at least with a static Huffman code
> >> (actually, there is no reason why this wouldn't work as well for
> >> Adaptive Huffman compression), to represent the last symbol in a
> >> message with fewer bits. This has to do with the fact that the Huffman
> >> codes for symbols have the prefix property. The last symbol does not
> >> need to have this property, since it doesn't have to contain the
> >> information of how many bits it contains - the representation has to
> >> stop when the message itself runs out of bits.
>
> >But exactly here Scott would oppose. (In my understanding) for him
> >any (correct) compression has to terminate in certain 'normal' way.
> >Any 'abnormality' would mean some information exploitable by the
> >analyst. Perhaps there is indeed some value, if your discussions with
> >him could be carried to a proper end.
>
> Well, there's no abnormality in the termination at this point: what
> happens is I'm switching from the Huffman alphabet to one suited to
> handling the last symbol: but a complete symbol is coded. This part of
> the procedure is one where we are in agreement.
So this symbol is one 'definite' symbol with a fixed number of bits.
This means that the last bit of this symbol is not necessarily (and is
often not) on a byte boundary. If I have understood properly so far,
let's pass to the following.
>
> The dispute between us, as I understand it, concerns the next step.
>
> The message, although shortened by a bit or two, still is contained in
> an arbitrary number of bits. Since it will be transmitted in bytes, or
> at least it is more convenient to encrypt in the form of whole bytes,
> he has proposed a coding scheme where a message having an arbitrary
> length can be represented efficiently by one that is made up of whole
> bytes.
>
> Since there are twice as many messages n+1 bits in length as there are
> messages n bits in length, if the probability of an n+1 bit long
> message were twice as high as that of an n bit message, there would be
> no problem with schemes of this type.
>
> Since, in actuality, the distribution of the lengths of messages
> follows a bell curve, the appropriate typical distribution for lengths
> from n to n+7 is a flat, uniform distribution of lengths. Thus, a code
> representing the left-over bits after the last whole byte of the
> message by a whole byte would have bias, since these left-over bits
> don't have equal probability; the longer strings are less probable.
What I don't yet understand is how one could use a 'probabilistic'
argument here. One has to take care of ALL possible cases (that
can occur) and not the most likely ones, nor even 'all but excepting
one case'. Or have I missed something essential?
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Scott Nelson)
Subject: Re: Intel 810 chipset Random Number Generator
Reply-To: [EMAIL PROTECTED]
Date: Mon, 10 Jan 2000 19:34:12 GMT
On 10 Jan 2000 00:36:31 EST, [EMAIL PROTECTED] (Guy Macon) wrote:
>
>Correct me if I am wrong, but it seems that the chip has a small processor
>or state machine in it that handles the memory cell programming and does
>a SHA1 hash on the output of the thermal noise source.
You're wrong, at least according to the white papers.
There's a software layer that does the SHA1.
>I can find no way
>to get at the unhashed data, and I don't have the source for the SHA1,
>which IMO puts this into the Security Through Obsurity category.
>
>I have a couple of questions about SHA1 in this application:
>
>[1]
>Does SHA1 put out more bits than it is seeded with? If so, how can we
>call those bits random?
>
SHA1 puts out 160 bits.
If it's only fed 32, than the output certainly doesn't meet
most definitions of random. But if it's fed more than 160,
then it does. From other comments in the document, I believe
they estimate 1/2 bit of entropy per bit of source, which
means they're feeding it 320 bits.
>[2]
>Does the nature of SHA1 match the behavior of variable delays between
>delivery of the random bytes?
>
No.
>[3]
>Is there any way to derive the input to the SHA1 from the output,
>and thus let me see the original thermal-random data?
>
Not if they did it right, but probably yes. :)
If, for example they hash the previous value of SHA1+
32 bits of new random number to generate a new value,
then given the previous value and the current value,
you can try all 2^32 possibilities and brute force
what the random value must have been.
It's probably moot though, the software layer
doesn't seem to be provided.
Scott Nelson <[EMAIL PROTECTED]>
------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Subject: Re: Example C programs to encrypt/decrypt password
Date: Mon, 10 Jan 2000 12:40:17 -0700
In article <01bf5b36$dc9e80c0$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
> Hi,
>
> I need to get sample of c programs to encrypt/decrypt password.
> I need those, because currently I use clear text passwords to access
> database application which is not secure, and will use compiled C programs
> to encrypt/decrypt the password. Thanks alot for your help.
In most cases, you don't want to encrypt or decrypt the passwords at
all. Instead, you want to hash the passwords. The basic idea is that
you store the result of hashing the password, and the compare the
result of hashing the entered password to the stored hash. If they're
the same, you assume the password was also correct. You normally use
a large, cryptographic hash (e.g. MD5 or SHA-1) so the chances of
being wrong about this are _extremely_ small (the chances of being
struck by lightning and winning the Lotto on the same day are quite a
bit better).
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
** 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
******************************
