Cryptography-Digest Digest #32, Volume #13 Sun, 29 Oct 00 05:13:01 EST
Contents:
quantum cryptography FAQ ("Daniel Bachofen")
Re: Psuedo-random number generator (Tim Tyler)
Re: DATA PADDING FOR ENCRYPTION (Bryan Olson)
Re: BEST BIJECTIVE RIJNDAEL YET? (Tim Tyler)
Re: Psuedo-random number generator (Tim Tyler)
Re: On introducing non-interoperability (Bryan Olson)
Re: Q: Computations in a Galois Field (Mok-Kong Shen)
Re: Is OPT the only encryption system that can be proved secure? (Mok-Kong Shen)
Re: how i decode this? (Paul Schlyter)
Re: DATA PADDING FOR ENCRYPTION (Tim Tyler)
Re: On introducing non-interoperability (Mok-Kong Shen)
Re: DMCA bans fair use (Ichinin)
Re: DATA PADDING FOR ENCRYPTION (Tim Tyler)
----------------------------------------------------------------------------
From: "Daniel Bachofen" <[EMAIL PROTECTED]>
Subject: quantum cryptography FAQ
Date: 29 Oct 2000 08:12:26 GMT
Reply-To: [EMAIL PROTECTED]
Hi,
I have some newbi-questions about quantum cryptography, but I could not
find any FAQ related to that topic.
I already read the cryptography-faq/part01-part10.
If anyone could give me a hint, to such a FAQ or a related newsgroup??
Thanks a lot
Daniel
[EMAIL PROTECTED]
(delete the _z if you want to contact me)
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Psuedo-random number generator
Reply-To: [EMAIL PROTECTED]
Date: Sun, 29 Oct 2000 08:12:38 GMT
David Schwartz <[EMAIL PROTECTED]> wrote:
:TR wrote:
:> This "phase noise" can of course be measured with special equipment.
:> But such measurements are vastly, vastly below what can be measured by
:> conventional software, which was the original claim, now conveniently
:> recalled for us here:
:>
:> >>>For a more realistic counterexample, consider true quantum randomness
:> >>>in the offsets between the CPU oscillator and the clock oscillator
:> >>>on a network card. This can be measured in software.
: Actually, the original claim was: [...]
[other stuff snipped]
Ritter's quote was spot on. Your quote looks like an attempt to change
the subject.
If you are going to try to split hairs about the word "original", you
should probably quote from the post at the head of the thread ;-|
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ ILOVEYOU.
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: DATA PADDING FOR ENCRYPTION
Date: Sun, 29 Oct 2000 08:16:35 GMT
Tim Tyler wrote:
> Bryan Olson wrote:
> : Tim Tyler wrote:
> :> Bryan Olson wrote:
>
> :> : [...] can you imagine someone so clueless as to expect his
message
> :> : space won't have enough redundancy to cover a couple hundred (or
> :> : several thousand) bits of key equivocation?
> :>
> :> Surely it is *very* easy to imagine such a case.
> :>
> :> What about the man sending short messages, for example?
>
> : "Message" yes, that's what the OTP is all about. "Messages"
> : sounds he doesn't really have a grasp of the requirements for
> : information theoretic security.
>
> Your implication that someone sending some short messages with a block
> cypher has a screw loose appears to be unwaranted.
I implied nothing of the sort. Use a unique IV, a modern
block cipher and a standard chaining and padding scheme.
If one does not trust computational security, then use
the OTP.
> I suppose you are suggesting he should be using an OTP,
> and not bothering with a padding scheme?
No. Just don't bother with the pointless non-standard
padding schemes.
> Using an OTP may require significantly more key material.
> Note that the redundancy you mentioned arises with messages
> longer than the unicity distance.
Wrong. It arises when the sum of the redundancy in
all the messages sent under the key exceeds the key
entropy.
> This may be significantly
> greater than the length of the normal block cypher's key.
>
> Consequently, using an OTP may require far larger keys than
> are on the cards.
>
> It's probably simpler to use a padding scheme that adds zero bytes of
> known plaintext to the message, thus avoiding the problem completely.
That's where you've made your mistake - moving away from
the standard padding schemes solves no problem.
> :> What about the man who forwards an encrypted message he has
> :> intercepted back to his HQ for decipherment?
>
> : Then he normally wouldn't even have a way to estimate the
> : redundancy.
>
> So he won't know "whether it has enough redundancy". Why
> should he be so clueless as to /expect/ that it doesn't have
> such a redundancy when he doesn't know much about his message.
That's my point. He has to expect his message space has
enough redundancy to cover the key equivocation.
> The attacker that intercepts his message may be unable to
> distinguish a correct decrypt from a random stream (without
> lots of work).
Huh? If he's forwarding intercepted messages, then there's
a small pool of possible plaintexts.
> Consequently adding up to 127 zero bits to the file might make
> finding a termination criteria much easier for him.
As John Myre wrote
Nobody with any sense cares, and you know why.
> Redundancy is only useful to attackers if they can detect it.
>
> It's not a case of whether /I/ can imagine someone so
> clueless as to have such expections - it's why /you/ can't
> see that a perfectly intelligent and rational person could
> have such expectations.
And yet your examples fail. You thought small messages
can't cover the unicity distance; not so since you can send
more than one. You thought intercepted encrypted messages
won't have useful redundancy. Did it occur to you that the
attacker could have intercepted the same messages, or that
the original sender is a likely attacker?
Might there be some case where one could achieve ideal
secrecy without a one-time random key? Perhaps. The point
is how clueless it is to design for that case.
--Bryan
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: BEST BIJECTIVE RIJNDAEL YET?
Reply-To: [EMAIL PROTECTED]
Date: Sun, 29 Oct 2000 08:27:55 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
: [EMAIL PROTECTED] wrote:
:> Tom St Denis <[EMAIL PROTECTED]> wrote:
:> : In article <[EMAIL PROTECTED]>,
:> : [EMAIL PROTECTED] wrote:
:> :> : Like I said I could use a OFB mode and do that... whoopy-doo.
:> :>
:> :> Not without compromising security - or signing everything.
:> :>
:> :> A server spitting out encrypted URLs to a client it has
:> :> established a shared secret with it may not necessarily *want* to
:> :> sign each message - since that is likely to bump up the bandwidth
:> :> and take longer to process.
:>
:> : You could use a HASH-MAC or something then.
:>
:> Adding a MAC to every message [causes problems]
:>
:> Why not avoid OFB, and totally avoid the problem arising in the first
:> place.
: Chances are if you use a block cipher and you are encrypting something
: trivial like a url changing a bit of the ciphertext will mess up the
: plaintext into some non-ascii block.
I guess an URL is not the ideal example to use with a bit-flipping attack.
In systems where there's a 1-1 mapping between plaintext bits and
cyphertext bits, the traditional example uses messages that
represent sums of money - where the change of changing $1,000,000
into a larger valid figure (if one knows the relative position of the
character) makes this worth doing.
If it helps you get your head around the problem of bit-flipping attacks,
consider the server dealing with numerous cash machine transactions
instead.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ ILOVEYOU.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Psuedo-random number generator
Reply-To: [EMAIL PROTECTED]
Date: Sun, 29 Oct 2000 08:43:01 GMT
Brian Wong <[EMAIL PROTECTED]> wrote:
: "Tom St Denis" <[EMAIL PROTECTED]> wrote in message
:> I would argue that even real life events are not totally random. The
:> decay of an atom is not predictable because we can't properly observe
:> it. [...]
: Then you would not understand quantum mechanics and why the decay
: of an arbitrary atom is indeed a random process and that there cannot be
: any hidden variables in the atom that we cannot observe that determine
: the time that the atom decays.
Not this old chestnut again ;-|
I'll /try/ to avoid arguing about the subject in this forum - but would
like to briefly say that this idea is thoroughly mistaken.
*Plenty* of modern deterministic physical theories exist, and are in
accord with the observed facts - as much as any other theory, anyway:
See Q13: http://www.anthropic-principle.com/preprints/manyworlds.html
for example.
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: On introducing non-interoperability
Date: Sun, 29 Oct 2000 08:51:43 GMT
Mok-Kong Shen wrote:
>
> Interoperability is the generally acknowledged benefit of
> standardization and is commonly to be strived at as best
> as possible. However, for a non-trivial amount of crypto
> applications, where there is a fixed communication path
> between two given partners, the interoperability needs
> only to exist between these alone, without requiring the
> same desirable property being extended to any third party.
> In fact, to the contrary, it is evidently very much to
> their benefit, if the opponent's system turns out to be
> not interoperable with theirs.
That's what cryptosystems do. They're designed so that
control of the keys provides exactly the interoperability
and non-interoperability desired. No hack-on obscurity
required.
--Bryan
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: Computations in a Galois Field
Date: Sun, 29 Oct 2000 10:17:25 +0100
Tom St Denis wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> >
> > Bob Silverman wrote:
> >
> > > Some polynomials most certainly ARE better than others. In
> particular
> > > a finite field is isomorphic to the quotient ring Z_p[x]/(g(X))
> > > where p is the field characteristic and (g(x)) is an ideal generated
> > > by a primitive polynomial. This is the polynomial you are looking
> > > for. It is much faster to choose a polynomial of low Hamming weight
> > > when choosing g(x) as this can make the arithmetic quite a bit
> > > faster.
> > >
> > > And optimal normal bases are even better (when they exist).
> >
> > I have a question of ignorance. If one uses the same
> > formulae, e.g. as in Rijndael, to define substitution,
> > would different primitive polynomials lead to substitutions
> > that have different desirable properties such as avalanche
> > etc.? If yes, would the computationally best polynomial also
> > be the best with respect to these properties? Thanks.
>
> Rijndael uses multiplicative inversion and all moduli of equal length
> which are irreducible will make sboxes of equal cryptographic
> properties. The sboxes will be different.
>
> You could always just use F(x) = ax^-1 + b in GF(2)^n to get a family
> of "cryptographically equivalent" sboxes with the same modulus.
I am interested how does one prove 'equal cryptographic
properties' or 'cryptographically equivalent' above. The
sboxes will be different, as you said. Do they have the
same avalanche? Could give a reference of your claim?
Thanks.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Is OPT the only encryption system that can be proved secure?
Date: Sun, 29 Oct 2000 10:17:41 +0100
Terry Ritter wrote:
>
> I do of course agree that mathematical models *can* help, but I do not
> agree that they *necessarily* help. This discussion of OTP's is one
> case in which the mathematical model provides nothing we can rely upon
> in practice.
I can't refute your claim with the word 'rely' above, if
it is to be understood in the absolute sense, and in fact
I myself often doubt whether certain theoretical
assumptions made in diverse contexts could be true in
practice at all. However, one could say that, the more
one approximates the theoretical model, the more likely
it is that the results from the theory are (approximately)
true. Now one can barely have an exact quantitative measure
of that 'approximation', at least in the case of OTP. But
still one can do some sensible, more or less subjective,
decision (based on one's evaluation/belief of that
approximation) with the aid of the theoretical results, I
suppose. Let's take an analogy. In material science, one
knows that there is nothing in practice that is perfectly
elastic. Yet there are materials that behave rather close
to that under sufficiently low loading and hence the
mathematical theory of elasticity can be of value (to some
extent) in practical design of machine parts etc. So, in
the OTP case, if we have a random source that we, after
considering the nature of the source and doing diverse
tests, believe to be a good approximation of OTP, then we
can have some confidence that a fairly high security
(not perfect security) is achieved, provided that no
error in the handling of that random source occurs. We
have 'proved' nothing but we do have met some practical
need. Perhaps another far-fetched analogy. A careful
check of an airplane before taking off doesn't ensure
absolute freedom of an accident but it does render it
highly improbable (according to one's belief, in the end).
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: how i decode this?
Date: 29 Oct 2000 09:04:38 +0100
In article <8teiah$ifv$[EMAIL PROTECTED]>,
Simon Johnson <[EMAIL PROTECTED]> wrote:
> In article <8tedm9$fjp$[EMAIL PROTECTED]>,
> Tom St Denis <[EMAIL PROTECTED]> wrote:
>> In article <[EMAIL PROTECTED]>,
>> Eduardo Hernandez <[EMAIL PROTECTED]> wrote:
>>> how i decode or decrypt this kind of messages???
>>>
>>> eg.
>>>
>>> MQ'(E<H8.=8"AKS*7C$$KTGXXF_-D:M+&![;'PY61C0<B$-?E1B.^XKPMT,:T
>>> MI38V9-JN7+H/[C2^9*R1&X`4;HUTLE$7D4D].B7JPZMTA2Z?;U9,^N$C8_C8
>>> ME?!/K?>7ZBM]H\OAPIPI+OR<S>::]>K<ESP$9RULS>)*[[@DAV:#LU\;+:'C
>>> MQH#&RZW06I'F7I^>QHD[!(_\_?DPX%&I`Y@NV9MZ!\%JD)8#%&YML5L>VG[6
>>> MCL^M[2!5+;[U\[?&[R%KO^T/&=V9,OV6-VI7G`K-Z&<-,.6_$VJZ&[#XE"6`
>>> M`:G/;Q3+T]+K8Q3^+KYQGEU-.2@A\IM6_E9Y)+&G!QO<];U:5P4/OC,E$TU]
>>> M`*@:H4DZVY?`B!&5%^OL_'O039X;>T[&K/U^7;E"&QPS$[.8R:[R:NI&)>/>
>>
>> It's a uuencoded message saying "Stop posting wierd garbage to
>> sci.crypt"
>>
>> Tom
>>
>> Sent via Deja.com http://www.deja.com/
>> Before you buy.
>>
> *LOL*, But on a serious note:
>
> We can't be expected to even attempt to solve the encrypted cipher text
> without knowledge of the algorithm.
So you mean it's a good idea to use secret enryption algorithms?
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: pausch at saaf dot se or paul.schlyter at ausys dot se
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: DATA PADDING FOR ENCRYPTION
Reply-To: [EMAIL PROTECTED]
Date: Sun, 29 Oct 2000 09:16:25 GMT
SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]> wrote:
: [EMAIL PROTECTED] (Tim Tyler) wrote in <[EMAIL PROTECTED]>:
:>SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]> wrote:
:>: [EMAIL PROTECTED] (Tim Tyler) wrote in <[EMAIL PROTECTED]>:
[what Applied Cryptography has to say about padding]
:>:>we also have a method which does not change the size of the message.
:>:>
:>:>The idea is to encrypt the last full block *again* truncate this to
:>:>the size of any short block at the end and XOR this with the plaintext
:>:>of the short block (rather than encrypting that with the cypher).
:>:>
:>:>This means that the OFB-like bit-flipping attacks can only be applied
:>:>to the short block at the end. (2nd e. p. 195 for details).
:>:>
:>:>This method gets a bijection - at the expense of not encrypting the
:>:>end of the file very securely.
:>
:>: Tim I may by wrong but I don't see how it gets a bijection of all
:>: 8 bit file to all 8 bit files. Example if the encrypted file is one
:>: byte long [...]
:>
:>The case of a single block is not explicitly mentioned.
:>
:>It can be dealt with (for example) by encryping a block of zeros
:>and XORing that with the plaintext.
:>
:>I.e. "encrypt the last full block *again* (or encrypt zero if there
:>is no full block in the first place)...".
:>
:>I believe this method gets a bijection - though any fractional last
:>block is susceptible to bitflipping attacks - and such problems would
:>not normally be tolerated.
: I am not saying thats its not possible, It is just that the
: procedure is incomplete and can't be directly bijective unless
: it tells explicitedly how to create an ecnrypted file shorter than
: a block. [...]
Applied cryptography is a kind-of chatty book. The author is describing
the algorithm, not presenting a full working algorithm. I expect he
would consider the case of a single block to be a simple degenerative
case.
Anyway, I missed out another important bit:
After describing the bitflipping problem, it goes on to say:
``Ciphertext stealing is a better way (see figure 9.5[snip ref]).
[snip description which makes little sense withouut the diagram]
The benefit of this method is that all the bits of the plaintext
go through the encryption algorithm.''
I believe this is bijective *provided* more than 1 block is present.
It seems that the plaintext and the cyphertext are always the same
length under such conditions, anyway.
It pads with (say) zeros, encrypts, and then uses some clever XORing
to make sure that truncating the cyphertext does not lose any
information.
AFAICS, ciphertext stealing does genuinely *not* work with short single
blocks.
http://www.io.com/~ritter/NEWS4/CTXSTEAL.HTM discusses the case of
applying ciphertext stealing to single blocks in more detail.
Ciphertext stealing in conjunction with OFB (i.e. simple XOR) for
single blocks would be bijective (I believe) - and it's weakness
would probably arise only infrequently in practice.
At any rate, this is the best traditional method of dealing with
the combination of large-power-of-two size block cyphers and real
world files that I have seen to date.
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: On introducing non-interoperability
Date: Sun, 29 Oct 2000 10:22:42 +0100
Bryan Olson wrote:
>
> Mok-Kong Shen wrote:
> >
> > Interoperability is the generally acknowledged benefit of
> > standardization and is commonly to be strived at as best
> > as possible. However, for a non-trivial amount of crypto
> > applications, where there is a fixed communication path
> > between two given partners, the interoperability needs
> > only to exist between these alone, without requiring the
> > same desirable property being extended to any third party.
> > In fact, to the contrary, it is evidently very much to
> > their benefit, if the opponent's system turns out to be
> > not interoperable with theirs.
>
> That's what cryptosystems do. They're designed so that
> control of the keys provides exactly the interoperability
> and non-interoperability desired. No hack-on obscurity
> required.
The idea is to obtain a system that differs from the
one the opponent has at hand. If the key scheduling
is modified, he wouldn't be able to do brute force,
for example.
M. K. Shen
------------------------------
From: Ichinin <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Crossposted-To: talk.politics.crypto
Subject: Re: DMCA bans fair use
Date: Sat, 28 Oct 2000 23:32:38 +0200
Dido Sevilla wrote:
> That is total BS. The United States wields such a great deal of power
> in today's world that legislation that happens in America winds up
> affecting the rest of the world more than anyone realizes, though
> technically, it shouldn't. If the DMCA really is just a U.S. law, then
> why in the name of all that is holy did Jon Johansen, who isn't a
> citizen or even a resident of the United States, get hassled the way he
> is just because he publicized DeCSS? Take note, he didn't even *write*
> the bloody thing. True, the law may not be worth a hill o' beans in
> Norway, but the kid got arrested and is under trial just the same. Why
> are even non-US sites being harassed for even linking to the DeCSS
> code? Like it or not, the United States and especially its corporations
> do have the kind of power to enforce their laws overseas if they see
> fit, and national borders don't mean a hill o' beans to them. To those
> of us who live in the Third World, the key words are "grand
> Imperialism."
But it wasn't the DMCA that was enforced, they (MPAA) simply contacted
the law enforcement (that chickened out, because they are afraid of Us
lawyers) in Norway and took own actions in fear of a legal battle. It
is sooo much simpler and sooo much more convenient to fry one individual
than to take a stand against corporate intrests that are stepping on
fair use which the whole world (-1 country) have. I think US lawyers are
amongst the worst scum of the earth, with terrorists and spammers.
Just look on the mouse patent thing (.SE vs .US), they did NOT deny the
patent, but it was a legal technicality that brought the whole thing
around,
and then Us companies are suing the patent holder for "hurting their
businesses".
So i ask: why the hell should the world respect patents and copyright if
not foreign P & C holders in Us are respected by Us intrests?
...And please, XOR this from sci.crypt.
/Ichinin
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: DATA PADDING FOR ENCRYPTION
Reply-To: [EMAIL PROTECTED]
Date: Sun, 29 Oct 2000 09:31:52 GMT
Bryan Olson <[EMAIL PROTECTED]> wrote:
:> This means that the OFB-like bit-flipping attacks can only
:> be applied to the short block at the end. (2nd e. p. 195
:> for details).
: Page 195 does not discuss attacks, only errors. [...]
Try reading it again:
``The weakness here is that while Mallory cannot recover the last
plaintext block, he can change it systematically by changing individual
bits in the ciphertext. If the last few bits of the cyphertext contain
essential information, this is a weakness.`` - page 195.
: None of the standard block chaining encryption modes detect
: modification. Use a MAC for authentication.
Bruce seems to think that bit-flipping attacks are a problem - and
consequently that resistance to them is a strength.
The reason is that block cyphers are their own (weak) authentication
mechanism - in that they often make it relatively obvious when the file
has been tampered with, by making two blocks (or sometimes the remainder
of the file) decrypt to garbage.
This is clearly a very imperfect authentication mechanism - but it's
a lot better than allowing flipping a single bit in the ciphertext
to affect the corresponding single bit in the plaintext.
Obviously this is only relevant when use of a MAC is prohibitively
expensive (in terms of processing, bandwidth, complexity, etc).
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ ILOVEYOU.
------------------------------
** 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
******************************
