Cryptography-Digest Digest #461, Volume #14 Mon, 28 May 01 10:13:00 EDT
Contents:
Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tim Tyler)
Re: The HDCP Semi Public-Key Algorithm (Munro Saunders)
Re: 2,2-multipermutation? (Tom St Denis)
Re: Good crypto or just good enough? ("Sam Simpson")
Re: rs232 data encryption (Mark Currie)
Re: Euroean commision will recommend all citizens to use encryption in email next
week, because of echelon. (Tony L. Svanstrom)
Re: Medical data confidentiality on network comms (Larry Kilgallen)
Re: Essay on "The need for a look at real life crypto" (Mark Currie)
Re: Good crypto or just good enough? (Stefan Lucks)
Re: Euroean commision will recommend all citizens to use encryption in email next
week, because of echelon. (SCOTT19U.ZIP_GUY)
Re: The HDCP Semi Public-Key Algorithm (ammendment) (Munro Saunders)
----------------------------------------------------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Reply-To: [EMAIL PROTECTED]
Date: Mon, 28 May 2001 09:12:25 GMT
John Savard <[EMAIL PROTECTED]> wrote:
: "Tom St Denis" <[EMAIL PROTECTED]> wrote, in part:
: Maybe there are some things about the conventional wisdom that need to
: be looked at, and some of the premises (really big keys, the algorithm
: being somehow unknown or variable) that amateurs keep bringing
: forwards have _some_ merit to them, even if the problems that can be
: pointed out in their proposals from the conventional viewpoint are
: also valid.
What are the problems from "the conventional viewpoint" that are pointed
out with the use of big keys?
Are you talking about key distribution problems? Or about an assertion
that keys much bigher the 128 bits are useless overkill?
Key distribution is indeed a problem - but I don't think anyone could
convinvingly argue that 128 bits is enough and more is pointless.
AFAICS, allowing variable size keys is not terribly painful in terms
of fattening up the key schedule. It seems like a good idea to me.
...or are you talking about keys that are much bigger than the messages? ;-)
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: Munro Saunders <[EMAIL PROTECTED]>
Subject: Re: The HDCP Semi Public-Key Algorithm
Date: Mon, 28 May 2001 19:45:22 +1000
[EMAIL PROTECTED] (Scott A Crosby) wrote in message
news:<[EMAIL PROTECTED]>...
> [EMAIL PROTECTED] (John Savard) wrote in message
news:<[EMAIL PROTECTED]>...
> > The description of the HDCP scheme at
> >
> > http://www.digital-cp.com/
> >
> > gives a simple shift-register based stream cipher that I believe to be
> > quite secure.
Maybe not as secure as it looks.
> http://cryptome.org/hdcp-weakness.htm
>
> For a description of the shared secret generation protocol, and the
> weaknesses in it.
I concur with this analysis (of the authentication protocol).
With the following observation ...
It appears that the system is designed to be imbedded on a chip with the
unique private keys hidden on the chip and never intentionally exported
(even to other chips on the same board).
So gaining access to these keys via hardware examination is beyond the
technology available to most of us. None the less, it would appear to be
"security through obscurity" and it will all end in tears.
But note also ...
I have examined the LFSR complex and discovered some tragic errors, note:
- the order in which the taps are used
- the identical offsets between taps 1 and 3 on LFSRs 3 and 4
By my (back off the envelope) calculations, about 11% of the time, the
output bits depend on only LFSRs 1 and 2. As a rough guess given two
sections of output less than 1000 bits length, separated by the cycle
length of LFSR 1 or 2, it all falls apart with a work factor of less
that about 2 ^ 17. There appear to be many similar attacks and I would
expect a complete analysis to show that this part is very weak.
NOTE: this is only one part of the system and the output bits I refer to
may not be available.
Regardless of the technical problems I think it is most important to be
critical of the political and social impact of these proposals (HDCP).
To the degree to which they are successful, they lead us towards a
world in which I wouldn't want to live. Corporations can only achieve
total control of their copyrighted material by achieving total control
of all technology, and in a modern world, all people. While they may not
succeed the battle will be very costly for people and profits.
We have to find another way.
Munro Saunders (munro at sw dot oz dot au)
This is absolutely a personal opinion and does not represent the position
of anyone else, including my employer (who has only the greatest respect ...).
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: 2,2-multipermutation?
Date: Mon, 28 May 2001 10:45:19 GMT
Serge Vaudenay wrote:
>
> Here b_new = a xor S[ a xor b ]
> and a_new = S[ a xor b ]
> where S is a permutation
>
> a_new is ok (it is a (2,1)-multipermutation)
> ( a_new , b_new ) is ok (it is a permutation)
> but b_new is ok iff for all b, a -> b_new is a permutation
>
> Actually, you can prove that this is a (2,2)-multipermutation iff S is
> an
> orthomorphism on GF(2^n) which means that both S and S[x] xor x are
> permutations.
Ok your method is slightly different than mine. Looks simple :-)
Thanks. (Have to go look up orthomorphism now(
Tom
>
> Serge
>
> Tom St Denis wrote:
> >
> > To get away from politics for a bit...
> >
> > Does the following pseudocode define a 2,1 Multipermutation? (a,b) forms
> > the input
> >
> > 1. a = a xor b
> > 2. a = S[a]
> > 3. b = b xor a
> > 4. b = S[b]
> >
> > Where S is some bijection. assume for no entries in S does S[a xor b] xor b
> > equal zero (i.e not linear enough).
> >
> > From what I can tell if 'b' or 'a' differs (not both) a will differ and
> > 2^n - 1 of the time (assume S is a n-bit function) b will not differ ...
> > hence it's not a 2,2 multipermutation.
> >
> > Is this true?
> > --
> > Tom St Denis
> > ---
> > http://tomstdenis.home.dhs.org
------------------------------
From: "Sam Simpson" <[EMAIL PROTECTED]>
Subject: Re: Good crypto or just good enough?
Date: Mon, 28 May 2001 12:25:04 +0100
"Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Tom St Denis wrote:
> > Technically 3DES is not DES though. It's incorrect to assume it
> > inherants all the *trust* of DES ...
>
> It's not hard to see that 3DES is no less secure than DES.
> Whether it is *much* more secure is, so far as I know, an
> open question. (Since it uses more key bits in additional
> series stages, it must be at least *slightly* more secure.)
Is this a suspicion or is there a proof for this somewhere?
> The incontrovertable fact is that 3DES is not feasibly
> brute-force searchable (yet) while DES is, so *everybody*
> (that matters) knows how to crack DES, but *not* everybody
> knows how to crack 3DES.
True, true....
Regards,
--
Sam Simpson
http://www.scramdisk.clara.net/
------------------------------
Subject: Re: rs232 data encryption
From: [EMAIL PROTECTED] (Mark Currie)
Date: 28 May 2001 11:45:49 GMT
Note to Robert Self,
If you use CFB, beware of the actual line bit ordering. Had a problem in the
past using CFB over a modem link. The Rockwell modem changes the bit ordering
for transmission. If you add/drop bits in this situation, you cannot re-synch.
Just warning you as it was not an easy problem to find. Needed to encrypt with
reverse bit ordering to solve the problem.
Mark
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
>
>"Scott Fluhrer" <[EMAIL PROTECTED]> wrote in message
news:<9ekhm2$egh$[EMAIL PROTECTED]>...
>> CTR mode doesn't automatically resync after add/drop errors (and with a
>> noisy RS-232 line, they happen). You could add explicit resyncing, but a)
>> that chews up bandwidth, b) that adds extra logic, and c) you also have to
>> worry about "what happens if the resync pattern just happens to occur in the
>> ciphertext"
>
>CTR mode will skip errors though. Let's say you are sending three bytes
>and the 2nd one gets noisy.... you will get 1X3.... Similar to CFB mode.
>
>Also CTR mode is not extra logic. You only need AESs encrypt routine, you
>actually encrypt the data via XOR.
>
>> There was a paper at FSE2001 by Alkassar et al about a CFB variant that
>> retained the resyncing property, but drastically reduced the expected number
>> of encryptions. However, I thought that the OP would prefer an
>> "off-the-shelf" solution, and in any case, 4000 block encryptions per second
>> is not pushing the state of the art, even with a moderately old
>> microprocessor. Of course, if it's an 8051, it probably isn't particularly
>> doable...
>>
>> >
>> > Again I feel CTR mode will win over CBC and CFB. Specially in this case
>> > since the low end cpu can do a single encryption per 16 bytes and still
>> gets
>> > the benefits of sending partial blocks and avoiding errors from killing
>> the
>> > entire stream.
>> CFB can handle partial blocks as well, and again, cannot resync from
>> add/drop errors.
>
>Well if you drop bytes CTR will lose. But for the most part CTR is faster.
>All you need need todo is check the sync every so often.
>
>Tom
------------------------------
Subject: Re: Euroean commision will recommend all citizens to use encryption in email
next week, because of echelon.
From: [EMAIL PROTECTED] (Tony L. Svanstrom)
Date: Mon, 28 May 2001 12:00:39 GMT
Crypto Neophyte <[EMAIL PROTECTED]> wrote:
> On Sun, 27 May 2001 16:31:16 +0000, John Savard wrote
> (in message <[EMAIL PROTECTED]>):
>
> > On Sun, 27 May 2001 13:22:56 GMT, [EMAIL PROTECTED] (Jan
> > Panteltje) wrote, in part:
> >
> >> It seems Echelon is used by the US and GB for industrial espionage,
> >> I suppose they (the commision) thinks that by everyone encrypting their
> >> email Echelon will become rather useles.
> >
> > And yet there was a recent news item that said Holland was planning to
> > follow the same path as Britain with its R.I.P. bill.
> >
> > John Savard
> > http://home.ecn.ab.ca/~jsavard/frhome.htm
>
> These are not mutually exclusive. My understanding of the RIP bill is that
> users are required to give up the passwords on demand, they can still use
> encryption.
> HKRIS
My understanding is that if they say that they no longer have the needed
key/password then it's up to the user to prove that they no longer have
access to the key/password; if they can't prove that then it's the same
as if the were to refuse to hand over the key/password.
Now how do you prove beyond any doubt that you've forgotten something...
/Tony
PS you're also not allowed to tell anyone that you've given up access to
said key/password...
--
########################################################################
I'm sorry, I'm sorry; actually, what I said was:
HOW WOULD YOU LIKE TO SUCK MY BALLS?
- South Park -
------------------------------
From: [EMAIL PROTECTED] (Larry Kilgallen)
Crossposted-To: comp.security.misc
Subject: Re: Medical data confidentiality on network comms
Date: 28 May 2001 08:46:39 -0500
In article <6biQ6.400$[EMAIL PROTECTED]>, "Roger Schlafly"
<[EMAIL PROTECTED]> writes:
> "Harris Georgiou" <[EMAIL PROTECTED]> wrote in message
> news:9es1cg$117j$[EMAIL PROTECTED]...
>> The fact that 128-bit ciphers where selected as minimum standard was what
> I
>> expected, but to my surprise too only 1024-bit keys where proposed for
>> asymmetric crypto and digital signatures/authentication. I guess I has to
> do
>> with hardware requirements (mostly on hardware devices), although no
>> signifficant difference in speed would emerge for any standard personal
>> computer.
>
> Personally, I'd be quite happy with 56-bit ciphers and 512-bit PK keys
> if the various other privacy leaks were plugged. The real medical privacy
> threats have almost nothing to do with crypto.
But some of them are susceptible to cryptographic controls.
Consider the issue of delegation. My doctor can see my
medical records. My doctor should be able to delegate
the ability to see those records to a specialist for a
limited amount of time, but without delegating unlimited
rights to further delegation. Some number of emergency
room doctors should be able to unseal my records in the
absence of my doctor if they all agree and the access is
strongly audited (alarmed) with guaranteed notification
to my doctor and me. These are all issues where there
might be some cryptographic assistance as part of the
total solution.
------------------------------
Subject: Re: Essay on "The need for a look at real life crypto"
From: [EMAIL PROTECTED] (Mark Currie)
Date: 28 May 2001 12:50:54 GMT
Good essay. However you state that exchanging public keys over the Internet is
"..completely non-applicable". I don't entirely agree with this. You can
exchange them over the internet, but you must verify the fingerprint over
another channel i.e. read them out to each other over the telephone. Granted
this only works when you know each other and there are many other pitfalls but
it needed mentioning.
Mark
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
>
>Based on my turn about look at computer security...
>
>http://tomstdenis.home.dhs.org/on.pdf
>
>Please comment if possible. Does this hit the mark with what you guys
>are thinking?
>
>Tom
------------------------------
From: Stefan Lucks <[EMAIL PROTECTED]>
Subject: Re: Good crypto or just good enough?
Date: Mon, 28 May 2001 15:19:08 +0200
On Sun, 27 May 2001, Tom St Denis wrote:
> Stefan Lucks wrote:
[...]
> > 5. How stable is the threat model? That means, if an application based
> > on the initial thread model is implemented, how soon may the point
> > come where users need an extended thread model.
> > (* Most of the time, users forget about the initial thread model and
> > continue to use an application when their security requirements
> > have changed.
> > *)
> > 6. If the threat model is unstable, how can we extend the thread model
> > and provide an application at not too much additional costs?
>
> This sounds very reasonable. BTW Are you a Pascal programmer?
Got me! Well, I used to be a Pascal programmer. Nowadays, I don't program
much at all, but if I write programs I use the language Oberon, which is
some kind of a Pascal grandchild.
(* But the comments are the same in Pascal and in Oberon. ;-) *)
> > I have recently seen an application where people encrypted their
> > plaintexts using triple DES in OFB mode. As it turned out, what they
> > really wanted was authentication, and they actually did not care much
> > about confidentiality. So using a single DES based CBC-MAC would have been
> > much better than encrypting under triple DES.
>
> For authentication I would have used a hash first ...
What is the purpose of a hash here?
Usually, a hash is an un-keyed primitive. Thus, the hash can be forged by
the same attacker who forges the message itself, i.e. by anyone with
(write-) access to the insecure channel. What is needed here is some kind
of a "keyed hash", i.e. a "message authentication code" (MAC).
This may be a (triple) DES based MAC like the CBC-MAC, or just as well
some MAC construction based on a dedicated hash function, e.g. HMAC.
> My original point was "within reason". If you had to pick between DES
> and Rijndael which would you choose? (Assuming all else is equal which
> admittedly doesn't happen ever)
I would certainly pick Rijndael. Assuming all else is equal, picking
single DES is unreasonable and shows bad engineering practice.
However, picking between triple DES and Rijndael is a different game ...
> > When it comes to using block ciphers, and assuming there are no very
> > limiting constraints about speed or (for hardware implementations) gate
> > count, a "good" block cipher ("good" as far as we know today) is not
> > significantly more expensive than a "bad" block cipher. So (with the above
> > exception) choosing a "bad" block cipher is bad engineering practice, even
> > if that "bad" block cipher seems to be just about "good enough" for the
> > current application.
>
> There are no "good" block ciphers, just "less badder". If we can break
> cipher X and not Y then Y is not as bad as X.
I agree. Note that I had put "good" and "bad" in quotation marks.
Being "good" or "bad" depends on current knowledge and (may depend) on
context, since improved attacks may show that a cipher is weak which has
been assumed to be "good" before, and some attacks (such as related key
attacks) may be considered irrelevant for some applications or threat
models.
--
Stefan Lucks Th. Informatik, Univ. Mannheim, 68131 Mannheim, Germany
e-mail: [EMAIL PROTECTED]
home: http://th.informatik.uni-mannheim.de/people/lucks/
====== I love the smell of Cryptanalysis in the morning! ======
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Euroean commision will recommend all citizens to use encryption in email
next week, because of echelon.
Date: 28 May 2001 13:29:56 GMT
[EMAIL PROTECTED] (Tony L. Svanstrom) wrote in
<[EMAIL PROTECTED]>:
>Crypto Neophyte <[EMAIL PROTECTED]> wrote:
>
>> On Sun, 27 May 2001 16:31:16 +0000, John Savard wrote
>> (in message <[EMAIL PROTECTED]>):
>>
>> > On Sun, 27 May 2001 13:22:56 GMT, [EMAIL PROTECTED] (Jan
>> > Panteltje) wrote, in part:
>> >
>> >> It seems Echelon is used by the US and GB for industrial espionage,
>> >> I suppose they (the commision) thinks that by everyone encrypting
>> >> their email Echelon will become rather useles.
>> >
>> > And yet there was a recent news item that said Holland was planning
>> > to follow the same path as Britain with its R.I.P. bill.
>> >
>> > John Savard
>> > http://home.ecn.ab.ca/~jsavard/frhome.htm
>>
>> These are not mutually exclusive. My understanding of the RIP bill is
>> that users are required to give up the passwords on demand, they can
>> still use encryption.
>> HKRIS
>
>My understanding is that if they say that they no longer have the needed
>key/password then it's up to the user to prove that they no longer have
>access to the key/password; if they can't prove that then it's the same
>as if the were to refuse to hand over the key/password.
>
>Now how do you prove beyond any doubt that you've forgotten something...
>
>
> /Tony
>PS you're also not allowed to tell anyone that you've given up access to
>said key/password...
I think it should be up to the governmetn. I have had several
PGP keys over the years. But floppies go bad and windows destroys
itself at lest a few times a year. So it should be obvious you
don't thave the keys.
I still think the safe way is to do one of the following
approachs.
1) Use a bijective compression program like BICOM for all your
real messages than any key will work.
2) combine the real encrypted messae with some phony message
such a wither other word is the encrypted messages. Every
Even word when XORED with the first word leads to some safe message.
3) Use the above and then still use PGP only save those keys so
the authorites can be happy when you give them the keys,
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM"
http://www.jim.com/jamesd/Kong/scott19u.zip
My website http://members.nbci.com/ecil/index.htm
My crypto code http://radiusnet.net/crypto/archive/scott/
MY Compression Page http://members.nbci.com/ecil/compress.htm
**NOTE FOR EMAIL drop the roman "five" ***
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged or
something..
No I'm not paranoid. You all think I'm paranoid, don't you!
------------------------------
From: [EMAIL PROTECTED] (Munro Saunders)
Subject: Re: The HDCP Semi Public-Key Algorithm (ammendment)
Date: 28 May 2001 06:59:31 -0700
I posted without the relevant documents in front of me and a few
resulting errors make a terse argument (almost totally) indecipherable ...
The taps are numbered 0, 1, 2, I should have refered to tap 0 and tap 2.
The LFSRs are numbered 3, 2, 1, 0. Numbers 1 and 0 have the same offset between
taps 0 and 2. Hence it is the cycle length of LFSR 3 and 2 which are
significant.
Munro Saunders <[EMAIL PROTECTED]> wrote in message news:<[EMAIL PROTECTED]>...
> I have examined the LFSR complex and discovered some tragic errors, note:
> - the order in which the taps are used
> - the identical offsets between taps 1 and 3 on LFSRs 3 and 4
> By my (back off the envelope) calculations, about 11% of the time, the
> output bits depend on only LFSRs 1 and 2. As a rough guess given two
> sections of output less than 1000 bits length, separated by the cycle
> length of LFSR 1 or 2, it all falls apart with a work factor of less
> that about 2 ^ 17. There appear to be many similar attacks and I would
> expect a complete analysis to show that this part is very weak.
> NOTE: this is only one part of the system and the output bits I refer to
> may not be available.
A more verbose explaination ... Refering to revision 1.0 of "High-bandwidth
Digital Content Protection System". See in particular "Table 4-1. LSFR
Generation and Tapping" and "Figure 4-3. LFSR Module Combiner Function".
At time t+0 the LFSR s have bit zero equal to R(i, t+0) bit 1 equal to R(i, t-1)
etc. The values at the tap0 s are xored together:
B(t+0) = R(3,t-5) ^ R(2,t-5) ^ R(1,t-4) ^ R(0,t-3)
and the result is fed into the shuffle network. At some point between 4 and an
infinite number of clocks later this same bit leaves the shuffle network.
The shuffle network is driven by the tap1 s. But for this argument we regard
the driving bits as uniformly random and independent. (This is not correct,
I beleive that any observation of nonindependence would allow even
stronger attacks). At each clock each
shuffle register outputs one of its two bits and replaces that bit with a
new input data bit. Which bit is output (and how it shufles) is determined by a
driving bit. There is a 50% chance that a bit entering a shuffle register
at time t will leave at time t+1; 25% at time t+2 etc. When we consider the
shuffle network as a whole the minimum delay is 4 and has a probability of 1/16.
Doing some precarious combinatorics by hand we find: (delay, probability),
(4, 1/16), (5, 1/8), (6, 5/32), (7, 5/32), (8, 35/256), (9, 56/512), (10, 5/64)
and 11 is left as an exercise for the student.
So at time t+9 there is an 11% chance that B(t+0) leaves the shuffle network.
Where it is xor ed with the then tap2 s:
O(t+9) = B(t) ^ R(3,t-16+9) ^ R(2,t-15+9) ^ R(1,t-13+9) ^ R(0,t-12+9)
O(t+9) = R(3,t-5)^R(2,t-5)^R(1,t-4)^R(0,t-3) ^
R(3,t-7)^R(2,t-6)^R(1,t-4)^R(0,t-3)
O(t+9) = R(3,t-5)^R(2,t-5) ^ R(3,t-7)^R(2,t-6)
and the output bit of the LFSR network (11% of the time) does not depend on
LSFR 1 or LFSR 0.
The contribution of LFSR 3 is R(3,t-5)^R(2,t-5) and this repeats (we hope)
with a period of (2 ** 17) - 1. Similarly the contribution of LFSR 2 repeats
with period (2 ** 16) - 1. If we can get output data seperated by (non 0)
multiples of either of these periods we can xor the output together and
we are left with a sequence depending only on one LFSR (2 or 3) with
a probability of about 1.2%. Any sequence of 84 bits will have 1 bit more
than average determined by LFSR (2 or 3), 1428 bits or so (guess) would allow
a correlation attack with a work factor of less than 2 ** 17.
After a guess on one of LFSR (2 or 3) a search can be make for the other
and the result confirmed on the non xored sequences with a much higher degree
of confidence. Once the state of LFSR 2 and 3 are know determining 1 and 0
are straight forward (I beleive, not specified).
I have used implicitely above the observation (guess) that the shuffle
network does not chance the cycle length of the LFSR network. I beleive
than any initial state will converge to the main cycle within an average
of 4 clocks and that it it very unlikely that any initial state stays away
from the main cycle for more than about 68 clocks. This allows us to often
avoid the difficultly of running the shuffle network backwards (run the
LFSR backwards r+68 steps, then with the shuffle network starting in any state,
run the whole network forward 68 steps, hmmm...). If you know the time at which
the key was set, stepping backwards the final steps, probably off the main
cycle, is precarious but possible. But it is also unnessary as all keying
information is in the LFSRs. The redundancies in the key setup can be
used to identify posible keys.
Noting that this is only part of the system and given the possiblity of
further mistakes by myself this still a rather devastating collapse.
Still I beleive better attacks are possible and I didn't use the
techniques of Golic (LNCS 658, p113-123, "Correlation Via Linear Sequential
Circuit Approximation of Combiners with Memory", 1993) simply because I
don't (yet) understand them (neither apparently did the system designers).
> Munro Saunders (munro at sw dot oz dot au)
> This is absolutely a personal opinion and does not represent the position
> of anyone else, including my employer (who has only the greatest respect ...).
Munro Saunders (munrosaunders at one dot net dot au)
------------------------------
** 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
******************************
