Cryptography-Digest Digest #60, Volume #13 Tue, 31 Oct 00 18:13:01 EST
Contents:
Re: Is RSA provably secure under some conditions? (David Wagner)
Re: [PGP] Twofish, 256bit, and Usenet Posting ("Michael Young")
Re: Psuedo-random number generator (Peter Maxwell)
Re: Rijndael file encryption question. ("mac")
Re: XOR based key exchange protocol - flawed? (David Wagner)
Re: DATA PADDING FOR ENCRYPTION (Bryan Olson)
Re: DMCA bans fair use (Secret Squirrel)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Is RSA provably secure under some conditions?
Date: 31 Oct 2000 22:14:20 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Roger Schlafly wrote:
>Which is why these folks shouldn't be claiming that they have proofs.
Is it acceptable to claim you have a proof when what you really mean
is that you can prove it secure under the assumption that factoring is
hard?
- If yes, then why not under other assumptions, too?
- If no, then note that there are no encryption systems with proofs
(excluding the one-time pad), so your criticism is not specific to
the random oracle model but applies to a vast field of theoretical
work in cryptography.
My first reaction is that you may be over-simplifying a situation which
is more complicated than you have given people credit for. Proofs
(perhaps better called "reductions", but let's stick with the common
terminology) are useful, even if they require unproven assumptions, so
long as the assumptions are reasonable and give us useful insights into
the properties of the cryptosystems of interest.
------------------------------
From: "Michael Young" <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp
Subject: Re: [PGP] Twofish, 256bit, and Usenet Posting
Date: Tue, 31 Oct 2000 17:00:53 -0500
>could you also give us the current method of chaining the main ciphers
>blocks, And does it still do a quick check to test if the key is correct
>so that it doesn't have to decode the whole file before rejecting a
>bad key.
PGP uses a CFB variant. Using a cipher with block size B, and an
input buffer size N (N<=B), generate the next N output bytes by
applying the base cipher to the last B output bytes (or zeroes if
there has been no output), XOR the first N resulting bytes with the
input, and emit those N bytes.
The data fed into this engine is as follows:
one block-size buffer of random data (N=B);
one buffer repeating just the last two *input* bytes (N=2);
user input data, block-size buffered (N=B until the last, where N<=B).
The first buffer effectively creates an IV. The second buffer provides
the quick check you're looking for.
A new format, introduced in PGP7, uses the same material, but
always buffers it in block-sized units (N=B).
All this is available in the OpenPGP specification (RFC2440, latest
draft available at imc.org).
------------------------------
From: Peter Maxwell <[EMAIL PROTECTED]>
Subject: Re: Psuedo-random number generator
Date: Tue, 31 Oct 2000 22:30:54 -0800
the issue of whether we use deterministic or wave theories doesn't really add any
light to the subject as the theories all effectively give the same results(to my
current knowledge).
the real curcial point in this argument(at least originally), seems to stem around
whether a quantum event is predictable or unpredictable. i see no evidence that
anyone has the ability to predict quantum events - without a clear experimental
demonstration that someone can infact presisely predict, say the decay timings of
an isotope, i would be comfortable in my beleif that quantum events are in fact
random.
P Maxwell
------------------------------
From: "mac" <[EMAIL PROTECTED]>
Subject: Re: Rijndael file encryption question.
Date: Tue, 31 Oct 2000 23:25:43 +0100
Hello!
I have the same problem and I posted it with subject "Newbie about
Rijndael" (10/31/00).
I was directed to Matt Timermanns code which is great. There are some other,
not so good but simpler methods. For example, if you have two byte string to
encrypt (block size = 16b) you can fill the last two bytes of a block with
your string and put the number of 'good' bytes (two in this example) in the
first byte of a block. You can fill the bytes between(2-14)with '0' for
example. When this block is decrypted you read the first byte and you know
the length of the 'good' string from the end of the file.
There are many different methods as there are many smart people out
there. But the main point here is the question of standard. If 'Bob' who is
encrypted data and the key being sent to, doesn't have the same
implementation of Rijndael (and the problem we discuss is solved
differently) he won't be able to decrypt parts of the text that didn't fit
in the size of a block. So, I think we are looking for the standard
technique (if there is some).
"ajd" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
> Hi,
>
> I've written a rijndael implementation (128 bit key, 10 rounds) and got it
> working with the test vectors. I now am trying to encrypt files with it.
>
> Say I have a text file msg.txt conatining:
>
> oh I do like to be beside the seaside.
> Oh I do like to be beside the sea.
> where the brass band pl
>
> This file is 99 bytes long. I want to encrypt it but the Rijndael block
> cipher requires blocks of 16 bytes, so I append the final block with
> gibberish (lets call this gibberish the 'carry'). Running this through my
> encryption algorithm gives an encrypted file of 112 bytes.
>
> Now here I could either
>
> a) chop off the carry before sending it to 'Bob' so my encrypted file
is
> back to the original 99 bytes. The problem here is that to decrypt you
need
> the same encrypted gibberish that the carry produced (which Bob doesn't
> know) result in losing the entire final block
> e.g decryption produces
>
> oh I do like to be beside the seaside.
> Oh I do like to be beside the sea.
> where the brass bandQLฦ
>
> We have lost the block which contained " pl"
>
> Or
> b) Save the entire final encrypted block before sending to Bob (so we
save
> 112 bytes of encrypted data instead of 99). The problem here is that Bob
> doesn't know how long the original encrypted file was. When he decrypts he
> then gets:
> oh I do like to be beside the seaside.
> Oh I do like to be beside the sea.
> where the brass band plอออออออออออออ
>
> We have the whole original method but some extra stuff as well. For
non-text
> files this could prove to be a problem. Do I use this method and send the
> file length to Bob as well or is there another way to get around the
> problem?
>
> Thanks for any help
> Andrew
>
>
>
>
>
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: XOR based key exchange protocol - flawed?
Date: 31 Oct 2000 22:33:43 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Mike Connell wrote:
>Pa, Pb are RSA public keys. (X)Pi means data X encrypted under key Pi.
>Xa, Xb are random blocks of data of the same size as the public keys.
>
>1. a -> b : Pa
>2. a <- a : Pb
>3. a -> b : (Xa)Pb
>4. a <- b : (Xb)Pa
>
>Then a and b compute the XOR of Pa,Pb,Xa,Xb. This gives them a
>substantional number of shared secret bytes to construct a session key
>from.
It does have some mildly funny properties (nothing earth-shattering).
Note that B can control what key they finally end up with. Bad?
I don't know. Maybe it's better to use hash(Xa,Xb,Pa,Pb), not XOR.
A reflection attack: Reflect A's messages back to himself.
1. a -> m : Pa
2. a <- m : Pa
3. a -> m : (Xa)Pa
4. a <- m : (Xa)Pa
Here M is the attacker. Note that A ends up sharing the key 0 with
himself, and if A sets up a "secure" channel using 0 to derive
encryption and MAC keys, we have two bad results: 1. M can send forged
messages over the channel, since M can predict the MAC key; 2. If A
sends anything over the "secure" channel, M can read it, since M can
predict the encryption key.
If you use RSA encryption, so that (Xa)Pb = Xa^Eb mod Nb (Pb = (Nb,Eb)),
then an active attacker M can break the scheme by replacing the
transmitted values (Xa)Pb with 0:
a -> b : Pa
a <- b : Pb
a -> m : (Xa)Pb
m -> b : 0
m <- b : (Xb)Pa
a <- m : 0
Then M can predict the session key used, since 0^Db mod Nb = 0, etc.
Also, a Denning-Sacco attack: Suppose M intercepts a session between
A and B:
a -> b : Pa
a <- b : Pb
a -> b : (Xa)Pb
a <- b : (Xb)Pa
M wants to know Xa XOR Xb. Next M can open a session with B,
replaying the old value of (Xa)Pb in message 3 of the new session:
m -> b : Pm
m <- b : Pb
m -> b : (Xa)Pb
m <- b : (Xb')Pm
M can decrypt message 4 to learn Xb'. Now suppose that somehow the
session key Xa XOR Xb' computed in the second session is revealed;
maybe you break a session key, maybe it is inadvertently leaked,
whatever. In any case, compromise of a single session key should not
result in a complete break of the system (that's the point of having
session keys). But in your proposal, revealing Xa XOR Xb' at any point
reveals Xa, which is halfway to compromising the old key Xa XOR Xb.
I don't think this is an especially good thing.
None of these are devastating, but they are worth a little thought.
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: DATA PADDING FOR ENCRYPTION
Date: Tue, 31 Oct 2000 22:46:52 GMT
Tim Tyler wrote:
> Bryan Olson wrote:
> : Tim Tyler wrote:
> :> Bryan Olson wrote:
> :> : Tim Tyler wrote:
> :> :> Bryan Olson <[EMAIL PROTECTED]> wrote:
> :> :> : Tim Tyler wrote:
>
> :> :> The problems of padding scheme of appending a 1 and padding
> :> :> with 0s to the end of the block is the topic under discussion
> :> :> I believe.
> :>
> :> : Specifically, you suggested that known plaintext it adds,
> :> : and thus the ability to reject most individual keys (out of
> :> : 2^128 of them) was some kind of security problem [...]
> :>
> :> That's a fair assessment.
>
> : [...]
> :> : One who cannot trust computational security might reasonably
> :> : use the OTP.
> :>
> :> If they can handle the large keys involved.
> :>
> :> : But presenting this as a justification for bijective padding is
> :> : nonsense.
> :>
> :> It's not nonsense. Failing to add known plaintext might help when
the
> :> attacker would not otherwise have a unique halting criterion.
> :>
> :> All he has to do is to guess keys ar random to stand an increased
> :> chance of success with his improved halting criterion.
> :>
> :> This isn't difficult to understand. What is your problem with it?
>
> : We already beat it. Exhaustive search is trivial to defeat.
>
> Guessing keys is going to work some of the time, nevertheless.
No. With a 256-bit key guessing has an insignificant
chance of working even once.
> If you are arguing that the advantage offered by an improved halting
> criterion is relatively small in the face of to difficulties imposed
> by a 128 bit key space, then you would be right - *IF* there are no
> attacks on the algorithm in question, and there are no other ways to
> get hold of key material besides cryptanalyic attack. Since neither
> of these can be known to be true there are other attacks besides
> brute force or guessing whith which the ability to reject keys helps.
If you need to disable known or chosen plaintext attacks,
then use a system that can do so. Bijective padding does
not.
>
> : If you think it's still to dangerous with 128 bit keys, or
> : that the attacker might know some, but not all, of the bits -
> : then use a 256-bit key.
>
> Bumping up the size of the key to provide security usually
> really helps.
> :> There you go with your "message spaces" again.
>
> : Yes. If you're seeking ideal secrecy without the OTP, then it
> : turns out to be pretty important.
>
> Of course - but in the context of this discussion, individual messages
> are what can be short - not whole spaces of messages. A single short
> message in a message space of millions of lengthy messages is
> liable to lack a concrete halting criterion - in the absence of
> padding slip-ups.
So your example actually does have millions of lengthy
messages in the message space? But you think it's
clue-ful to expect the messages will not have enough
redundancy to resolve the key, because there are some
short ones too?
> :> If each messag has its own key, message spaces are of little
> :> relevance.
>
> : That's one of my points. Use techniques that work for all
> : message spaces.
>
> Somehow you manage to completely ignore the point I'm raising and
> go off in a new direction.
>
> To repeat it again - a short message can be within the unicity
> distance by itself - if it comes with its own key. Message
> spaces matter not in the slightest to this issue. All that is
> relevant is the transmission of the individual message in question.
> :> Regardless of what you thought you were talking about, my
> :> point still stands - short messages may not contain enough
> :> entropy to allow a unique halting criterion. If you pad them
> :> out with lots of zero bits, that may make the difference
> :> between having a single unique possible message, and
> :> having many such possible messages.
>
> : And your point is still nonsense. Halting criteria is no
> : problem. Use a large enough key.
>
> Your objection appears to be nonsensical and contradictory! ;-)
>
> Using a large enough key *makes* halting criteria a problem.
>
> Your whole argument to date has been that the attacker can
> always get hold of a halting criterion, even without padding.
> If you now say "use a large enough key" to ensure no halting
> criterion exists, you seem to be sabotaging your own argument.
Ah, I should have been more specific. Use a key large
enough that even with a halting criteria key-trial is
useless.
> : Note that the one-bit followed by enough zeros to fill the
> : block differs trivially from a bijection.
>
> There's a categorial difference - one is a padding scheme
> - and the other is a mapping between two sets ;-)
How does the way you choose to categorize them limit
an attacker?
> : Any message that does not end with an all-zero block is the padded
> : image of some bit-string.
>
> Sounds a bit wasteful. Why not do what you suggested and
> use "a one-bit followed by enough zeros to fill the block."
I think this is a mis-communication again. That's the
scheme I'm talking about. If we view the padding as a
mapping from bit-strings to strings consisting of whole
blocks, the only members of the range not in the image are
those ending with an all-zero block (well, also the empty
string).
> Better still, why not use a bijective mapping between
> the set of 8-bits files, and files with the desired block
> size.
One could. The fact that it's bijective between those
two sets does not mean that it doesn't add redundancy.
Not to worry though - real world message spaces have
a lot of redundancy anyway, so our ciphers are designed
to handle it.
> :> : Very short messages happens frequently; for example an
> :> : encrypted telnet session often sends individual key-strokes.
> :>
> :> : Do you know someone sending very-small messages with a new
> :> : small key every time?
> :>
> :> I believe you can send messages of any size with PGP.
>
> : Yes, I noted public key systems in the previous post, and that
> : they have a unicity distance of zero, so no message is short
> : enough.
>
> You mentioned symmetric key distribution using PK systems.
>
> Once a symmetric key has been distributed, what then?
Then you are already among the "some people" in:
It is true that some people are prepared to trust
security based on the percieved difficulty of performing
certain mathematical operations, rather than security
based on an information theoretical lack of ability to
determine whether keys are correct.
[...]
> : And do you actually know anyone sending only one message with
> : each PGP key?
>
> With each PGP *session* key? Yes.
> AFAIK, everyone who uses PGP does this.
So if you strip off the public key encryption, then
send the session key encrypted messages, and transport
the unique session key by some out-of-band channel,
then for very short messages you would have a case
where the messages do not cover the unicity distance.
Do you know anyone who does that?
[...]
> :> : "Intercepted" means it came from an adversary. We're not
> :> : talking about how the user might get lucky and not be
> :> : attacked by that adversary. [...]
> :>
> :> I was not talking about that either. I was saying that
> :> some attackers
> :> might not have the information necessary to mount the attack you
> :> suggested. Consequently, defending against their (weaker) attacks
> :> may still be worthwhile.
>
> : As I wrote in the snipped part, one has to defend against
> : chosen-plaintext in this case, where bijective padding is
> : useless at best. Expecting that the message space won't have
> : enough redundancy is clearly wrong if _any_ adversary knows
> : the plaintext.
>
> Obviously. Equally obviously, the contingent "if" need
> not be true.
>
> : This example fails big.
>
> No - you've still just failed to grasp it.
Not through lack of trying. Where did I misunderstand? These
are intercepted encrypted messages. The plaintext of your
messages is the intercepted ciphertext. You cited this as a
case in which it would be reasonable (non-clueless) to
expect our messages did not cover the unicity distance of a
conventional cipher.
If we're intercepting these messages, an adversary supplies
our plaintext. We have to expect not only known, but chosen
plaintext attacks. Bijectively transforming chosen
plaintext just means that the attacker can choose every
bit of the post-padded message.
> : [...]
> :> Nope. People can and do send short messages, and change key
> :> before they exceed the unicity distance. Deal with it.
>
> : Yet the only one you named, when specifically asked if you
> : could, was PGP.
>
> Yes.
>
> : It's public key - unicity distance zero.
>
> "Unicity distance of zero" only applies to the distributed session
> key.
More importantly, it applies to the message as people
actually send it. It makes no sense to say we must not
provide known plaintext and then use a public-key cipher.
--Bryan
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
Date: 31 Oct 2000 23:08:16 -0000
Crossposted-To: talk.politics.crypto
Subject: Re: DMCA bans fair use
From: Secret Squirrel <[EMAIL PROTECTED]>
I agree. In fact I am opening a shop to damage so people
can have their access-control-protected works damaged at
arm's length. Damage-er-us.com I'm thinking of calling it.
In article <8tlii8$n8f$[EMAIL PROTECTED]>
[EMAIL PROTECTED] (Jeff Makey) wrote:
>
> In article <[EMAIL PROTECTED]>,
> Roger Schlafly <[EMAIL PROTECTED]> wrote:
> >The Copyright Office just declared that only two classes
> >of works are exempted from prohibition against circumvention.
> >They are:
> [...]
> > (2) Literary works, including computer programs and databases,
> >protected by access control mechanisms that fail to permit access
> >because of malfunction, damage or obsoleteness.
>
> I predict that we will soon begin to hear stories about
> access-control-protected works that have mysteriously been damaged.
> The nature of the damage will be such that a licensed access device
> will fail to properly provide access to the work, yet the
copyrighted
> material on the media will remain substantially intact.
>
> I further predict that these stories will be followed by tales of
> successful efforts to legally extract the copyrighted works from the
> damaged media. These tales will no doubt go into great detail about
> the damage to the media and the recovery procedure. For example,
one
> of these tales might include a sentence like this:
>
> "If your DVD of _The_Matrix_ has a scratch exactly like figure A,
you
> can still watch it on your Linux box using the scratched_matrix.c
> program even though it will no longer play in your DVD player."
>
> :: Jeff Makey
> [EMAIL PROTECTED]
>
> Department of Tautological Pleonasms and Superfluous Redundancies
Department
------------------------------
** 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
******************************
