Cryptography-Digest Digest #771, Volume #10 Mon, 20 Dec 99 01:13:01 EST
Contents:
Re: S-Box evolution (lordcow77)
Re: compression & encryption (lordcow77)
Re: S-Box evolution (Scott Fluhrer)
I was wrong and I apologize (Was: SRP - a secure alternative for authentication >>
Nice reading) ("rosi")
Re: S-Box evolution (Scott Fluhrer)
Re: Keystrokes monitored/encryption useless (molypoly)
simple rng idea (Tom St Denis)
Re: simple rng idea (Tom St Denis)
Re: Cryptanalysis (David Hopwood)
----------------------------------------------------------------------------
From: lordcow77 <[EMAIL PROTECTED]>
Subject: Re: S-Box evolution
Date: Sun, 19 Dec 1999 20:12:35 -0800
In the version of sbox.c that I have (last modified June 2 1998) found
on the original AES CD, the min is initialized to an absurdly high
value (ie. > 1) considering that it should represent the single-bit
correlation of the S-box. Later, in the segment
new = correlation(sbox,tests);
if (new < min) {
if (!fail(sbox,tests)) {
memcpy((char *)best, (char *)sbox, sizeof(best));
memcpy((char *)besttests, (char *)tests,
sizeof(besttests));
***** if (min > .55) /* I changed this */
showbest(j+1,failures,j,best,besttests);
min = new;
The comparison in line marked by the stars is incorrect and can never
fire before min is ABOVE some other absurdly high number > 100. I'll
have to dig up the code if you want more details. Rather odd.
In article <83k52u$6po$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (David Wagner) wrote:
> In article <[EMAIL PROTECTED]>,
> lordcow77 <[EMAIL PROTECTED]> wrote:
> > Flaw detection isn't unfeasible if the S-box is reasonably
> large. The
> > AES candidate MARS has a program for generating and testing 8x32
> > S-boxes, although it does take quite a long time to find one and
> there
> > are some bugs in the code.
> Can you say anything more about the bugs in the MARS S-box testing
> code?
> Any details, descriptions of the buggy cases, etc. would be very
> interesting.
> Thanks!
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: lordcow77 <[EMAIL PROTECTED]>
Subject: Re: compression & encryption
Date: Sun, 19 Dec 1999 20:15:58 -0800
Show me a modern block cipher so throughly broken that one can use
known-plaintext characteristics of the first two bytes of the block to
reduce the keysearch space and I'll show you a block cipher that one
should never use. Or better yet, give me an ACTUAL EXAMPLE of such an
"attack" on any reasonable block cipher construction, even a badly
broken one like FEAL-4.
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: Scott Fluhrer <[EMAIL PROTECTED]>
Subject: Re: S-Box evolution
Date: Mon, 20 Dec 1999 04:54:34 GMT
In article <[EMAIL PROTECTED]>,
Tim Tyler <[EMAIL PROTECTED]> wrote:
>
>Doing things dynamically with your s-boxes /may/ mean too much work
>at runtime - given the set of constraints s-boxes usually have to
>operate under.
And it depends a bit on the design of the rest of the cipher. If
the design is such that a straight-forward implementation of the
sbox is a simple array is practical, then tweaking it on the fly
may be workable.
(To the OP): Remember, however, that changing the sbox also takes
time which needs to be included when computing the time-to-encrypt.
So, you need to show (or assume) that having a dynamically varying
sbox allows you to simplify (speed up) the cipher enough to justify
adding in the modify-sbox code
>
>/Perhaps/ cycling through a predetermined list would be enough for
>whatever security benefits you're trying to obtain.
Actually, this strikes me as even worse than having a single fixed
(well chosen) one -- the attacker can attack all of them in parallel,
and so the strength of the cipher is the strength of your *weakest*
sbox.
--
poncho
------------------------------
From: "rosi" <[EMAIL PROTECTED]>
Subject: I was wrong and I apologize (Was: SRP - a secure alternative for
authentication >> Nice reading)
Date: Mon, 20 Dec 1999 00:10:11 -0500
(Please see NOTE at end, if interested, for reason why
this is not attached to the appropriate thread)
Dear Tom,
Thank you very much for the post.
My reply has six parts:
1. Apologies
2. A few words about my confusion
3. Questions concerning the patent status of SRP
4. Mind your s's and v's
5. EZK
6. Seeking interest in Quasi-Public Keying
Of the 6, only 1 is relavent. Others are for other purposes
(lumped in one post instead of several due to lazy habit :)).
1. Apologies
First and foremost, I apologize for my confusion which
must have confused many others. As you pointed out, I
was obviously wrong. Thank you for the nice clarification.
2. A few words about my confusion
I think I asked and stated a couple of things. Sometimes,
if one chooses to answer some but not all of the pionts raised,
the picture may be a bit skewed. I think I mentioned the
mixed use of password and verifier and I also mentioned
people _new_ to cryptography. Of course, with your nice
clarification, I see exactly where I was wrong. I could have
read carefully to know that "to establish a password with
Steve" (page 6) should really mean "to securely send Steve
a verifier (touple) to be safely stored at Steve's", and I
should not have treated the word random the same for s
and a-b. I should have come to clear understanding that
s is arbitrary but FIXED (in the sense that it stays constant
but unique in relation to v, the verifier for Steve). This
truly sounds like word game I am playing rather than anything
of substance (and my interest was not really there, anyway).
I said, I believe, I was being picky. I also could have said
inaccurate things at places. But if it is not accurate, it is
not.
I repeat that I was being picky. I thought it could be a
nicer reading if it is refined (maybe I was wrong there as
well); I believe I once recommended SRP in this group to
some one asking for a protocol and I do not believe that I
did the same with any other protocol (even though it
should not suggest at all that others are in any sense
inferior). I think SRP remarkable. I can not defame SRP. No
person can and, in fact, no God can (be that crypto god or
God of all gods). SRP is just as good as it is. But (a BIG
BUT), if it is not to my satisfaction, it is NOT. I could
not have said otherwise for then I would be one of the
biggest liars in the world.
However, let this be very, very clear to everyone. This
by no means suggests that any protocol should be designed
to satisfy me or that if it does not satisfy me it is no good.
Above all, my dissatisfaction does not mean that I have
anything better, or even there can be anything better. It
just means that I am not satisfied.
I do not demand or expect you to say anything about
the mixed use of password and verifier. If I do, I am more
sure than anything that I am petty. (After disappointed
with mathematics a bit, I sought another universal language
in its place. I tried music. :)) And I am reminded of
Tchaikovsky's words about his first piano concerto. You
know, not changing a single note, it would have been
just as great a piece (even though some people may
believe that he did make some changes).
3. A few questions about the patent status of SRP
Again, you may choose not to answer my questions.
But your answer(s) will be truly greatly appreciated. I
thank you sincerely in advance.
What is the patent status of SRP?
The post I was responding to mentioned that MIT
was in the (mind ?) process of patenting it. I am not
sure when that started, if at all. I am sure that I did
not read all your posts requesting comments on various
versions of SRP. What I am interested in is how the
patent office (USPTO, I mean) treats the first disclosure
date. Any ideas?
Love to hear any other things that you believe are
of interest concerning its patenting. Thanks.
4. Mind your s's and v's
This is about something of interest, IMO. And I
do not believe that it is not obvious.
If s was termed arbitrary but constant (and
unique to v), it may be easier for people to relate
it to an identity-based version. But then how x is
derived will change. Will it? Any ideas? By the
way, does s have to be generated from a 'true'
random generator or a very good prandom generator?
Now the more interesting one: v.
I believe you mentioned that knowing v, an
attacker can potentially do some damage. He can
impersonate Steve.
I am not satisfied about the above. Why give
v that kind of vulnerability? Why can't we give
an attacker no clue from anything we store? I am
aware (s, v) may be further protected by another
security mechanism, but that then depends on
the security of that mechanism, a whole new can
of novel worms. In addition, I do not know if that
protection mechanism can be provably secure.
(Sorry, need a word about provably. I do mean
provably. I do not mean provably based on the
not yet proven hard problems.) If it does, you
did not mention. Would you care to tell if there
is anything implicit about those protections?
Let me look at it under different lights and
you may give us a bit of your opinions. But let
us first lay down our assumptions:
1. P (the password not verifier) is not
exposed.
2. x is not derivable in a better way than a
guess.
3. v is securely stored (i.e. an attacker can
not obtain it either passively or actively
such as access the form v is stored and
crack the protection on v, if any).
4. modular discrete logarithm is hard.
5. H (the hash) is one-way.
We will try to remove some (but not all) of
the assumptions and see if we get something
better. (Please note that it does not imply
that we can actually remove any of these, but
just for analysis purposes, we make the removals
assumptions. You said you welcome formal
analysis. Unfortunately, my poor math will do
a worse job. Forgive me for being informal.)
Removing 3, we get what you seem to say a
system where impersonation of Steve is possible
and attack on x may be much easier (than without
removing 3). Do you agree that this is a somewhat
vulnerability?
There is one thing very obvious but I feel
that you did not state, or at least did not make
explicit. That is g^z as verifier stored at
Carol's place AND verifhying both ways AND
the hash of the two resulting session keys
established by executing the protocol in both
directions as the actual established secret/
session-key.
Removing 3 double-sided. Now, things gets
bleaker. The above, even secures when one side
has its v 'lost to the attacker', fails kind
of miserably to MIMA (Man-in-the-middle-attack)
in this situation. This is of course a special
type of MIMA, in fact, double impersonation.
Let me cut in with something. The problem
with the situation (with removal of 3) is that
the initiator of the protocol can be left in
doubt. Even though Steve is, at the end of the
protocol, sure he is talking to Carol, Carol
may have unremovable double if v is stolen. If
the initiator can get assurance, he/she can
just initiate a round of the protocol to make
sure. Unfortunately, when it is the initiator
who is left unsure, the thing looks quite
hopeless (strictly in that situation!).
Removing 3 (single- or double-side). If
an attack succeeds in obtaining x, damage could
be more severe in the corresponding mode of
protocol execution. But this requires the
removal of 4. In this case, the attack is not
even necessarily an active one and is the most
horrible one one can enjoy.
Furthermore, if P is of a certain type, e.g.
small, low entropy, etc., (in addition to the
removal of 3 and 4) and from x P can be attacked,
it would be truly a disaster (especially if P is
the 'master' secret).
I seem to apply scare tactics. Well, maybe.
But see, 3 and 4 may not be guaranteed. If there
is something provable that ensures 3 and/or 4, I
do not know. Can anyone shed some light here? I
would really appreciate.
Now a bit more practical and restricting to
what you have (i.e. making no more assumptions
than you do) and using the special type of
'public' keying method, namely discrete log,
can we find a way to do better? I may be asking
too much, or may be not. I just wonder if any
one can enlighten us a bit. Tom, you have the
most experience with your scheme and seem to
know very well about this particular ZK
realization, could you share with us a solution
to what I discussed, or with some improvement
that alleviates the potential threat we can face?
I believe I said that I have nothing better.
But now _suppose_ there is a solution that
requires (for each protocol execution) exactly
one more hash, and one more exponentiation, and
one more 'quite negligible' operation, would
that satisfy anybody (a bit more)? Of course,
this is inferior. There is a considerable
% more computation (for the "one-more's"). We
assume the least disruption to your basic
scheme but implementation details will be
different.
Anybody knows anything along this line?
Anything better (than having the three 'one-
mores')? Anything, even a partial solution or
some incomplete thoughts? Thanks.
5. EZK
This can be pronounced 'easy knowledge',
but it really stands for 'Extented Zero-
Knowledge' and extented is in a special
sense.
My understanding of ZK is roughly that
passive listening onto the conversation is
to result in non-increasing knowledge about
what is being communicated. This is achieved
in, for just one example, SRP. SRP does more
and unless one is truly confused, one should
obviously see :).
Now if v is even immune to active attacks
of some more 'applicable' types, the ZK
concept is in some 'homemade' sense extended.
Here, of course, caution must be issued. The
word 'applicable' excludes some types of
active attacks, such as rubber-hose. To be
concrete, even if the attacker has v (and of
course assuming he can crack discrete log
as well), he should still be unable to progress
any further. That is what I call immune. But
immune is in the sense that it is PROVABLE.
Provable is not to depend on a 'hard' problem
as I previously mentioned. It is either a
number theoretic result (hypothesis is NOT
a theoretical result) or an information
theoretic result.
Lastly for this section, I deliberately
made it confusing. Complaints here will
NOT make me mad :).
6. Seeking interest in Quasi-Public Keying
(Totally unrelated to SRP)
I would like to get information, ideas,
interest in QPK which roughly means:
An asymmetric encryption key
may have more than one possible
decryption keys that decrypt
any ciphertext to different
versions of corresponding
plaintext.
Important: asymmetric can be based on
one of those 'hard' problems.
Does anybody know if anybody is doing,
has done something in that direction? Even
contemplating on similar concepts? I am kind
of desparate in need of ideas and enlightment.
I have a version that I conjecture to be
working. However, it seems very, very wasteful.
Huge key(s), many-rounds protocol, etc.
Any information, a pointer for example, will
be greatly appreciated.
Thanks
--- (My Signature)
NOTE: Can not find Tom's reply post any more.
I swear to have read it (on Monday
perhaps?) Hurt my thumb laying down
plywood preparing for flooring and
did not read mail/news for quite a couple
of days. Sorry for the late reply, Tom.
I also posted some corrections to
my post along the thread started by
KloroX. Can not see that either. I
am sorry for the errors. Please do
be critical of what I said and
correct the errors. Thanks
------------------------------
From: Scott Fluhrer <[EMAIL PROTECTED]>
Subject: Re: S-Box evolution
Date: Mon, 20 Dec 1999 05:07:15 GMT
In article <83kcg1$12b$[EMAIL PROTECTED]>,
Scott Fluhrer <[EMAIL PROTECTED]> wrote:
>
>(To the OP): Remember, however, that changing the sbox also takes
>time which needs to be included when computing the time-to-encrypt.
>So, you need to show (or assume) that having a dynamically varying
>sbox allows you to simplify (speed up) the cipher enough to justify
>adding in the modify-sbox code
Sorry to respond to my own post, but I just realized: you have to
be very careful how you modify the sbox. Suppose we are talking
about the block-cipher-like design (with changing sboxes, it's not a
classical block-cipher), and you limit yourself to small changes
(perhaps one sbox element at a time). Then, the attacker sends through
two identical plaintext blocks, one before the change and one after.
If the sbox change is small, the two resulting ciphertexts may be
different due to changes in the last few rounds, and so by studying
how the ciphertexts differ, the attacker might very well learn
deep secrets about the internal workings of the cipher at that point.
This is a Very Bad Thing.
--
poncho
------------------------------
From: molypoly <[EMAIL PROTECTED]>
Subject: Re: Keystrokes monitored/encryption useless
Date: Mon, 20 Dec 1999 05:05:51 GMT
> I like to run a couple of 30AWG wire wrap wires into the plug on the
> back of your PC and connect a Basic Stamp [
http://www.parallaxinc.com/ ]
> and have it record keystrokes. It's about the size of a postage
stamp,
> and there are cool RF transmitter modules available. This allows me
to
> get the NT Logon password, which no sniffer program can get. For that
> matter. there are TX cameras that look through pinholes in your walls
> or ceiling. I could make a video of your hands on the keyboard and
> of what is displayed on your screen.
>
> If you don't secure your computer physically, I can defeat any
security
> system you install with little trouble.
>
>
You're one sick puppy . . . what else do you do with those cameras?
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: simple rng idea
Date: Mon, 20 Dec 1999 05:17:25 GMT
Ok here is an idea to play with.
You have f() which returns the next number from a prng [say a Lagged
Fibonacii generator].
You then reduce it modulo 5. If the result is >= 2 then you ditch it
otherwise return the lsb of the result. The pseudo code resembles
1. a = f()
2. if (a mod 5) >= 2, goto 1
3. output (a mod 2)
This resembles a shrinking generator to me... any ideas?
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: simple rng idea
Date: Mon, 20 Dec 1999 05:24:35 GMT
In article <83ke53$9eo$[EMAIL PROTECTED]>,
Tom St Denis <[EMAIL PROTECTED]> wrote:
> Ok here is an idea to play with.
>
> You have f() which returns the next number from a prng [say a Lagged
> Fibonacii generator].
>
> You then reduce it modulo 5. If the result is >= 2 then you ditch it
> otherwise return the lsb of the result. The pseudo code resembles
>
> 1. a = f()
> 2. if (a mod 5) >= 2, goto 1
> 3. output (a mod 2)
>
> This resembles a shrinking generator to me... any ideas?
And could this idea be expanded to returning octets? Such as mod 521,
then mod 256 instead?
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
Date: Mon, 20 Dec 1999 05:11:12 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Cryptanalysis
=====BEGIN PGP SIGNED MESSAGE=====
[EMAIL PROTECTED] wrote:
>
> I'm doing a paper on Cryptography and It's Affect On The Information
^^^^ should be Its
> Age. It's mostly about crypto in regards to current US law,
Now is not a particularly good time to do that, bearing in mind that the
law appears to be going to change quite radically in January (although
we don't have the full details yet).
> however, I have a brief primer on crypto in the first few pages.
> I need to source everything that is not an opinion. I remember reading
> something a few weeks ago about how cryptosystems are often created to
> meet a purpose and you wouldn't use a difficult cryptosystem to apply
> to a message to send info that will expire in one week.
You may have read that, but you should also be aware that many practicing
cryptographers strongly disagree with it. Here are five reasons why:
1. The length of time to break an algorithm (if it is feasible to break)
depends on how much processing power the attacker has, which in
general you don't know. It's not possible to create a cryptosystem
that is 'only just strong enough' to last a particular length of time.
We (that is, the public cryptographic community, and probably the
private one as well) don't even know how to create a system that is
'only just strong enough' to require a given amount of work to break.
In that situation, the only sensible strategy is over-engineering.
2. Historically, algorithms that were not designed from the start to have
conservative security goals have fared very poorly. If they are broken,
they tend to be broken catastrophically.
3. For symmetric crypto, in particular, it costs very little if anything
to use a very strong algorithm as opposed to a weak algorithm, or as
opposed to one that seems to be on the edge of being breakable. For
public key algorithms, longer keys do require more processing time,
but you can choose *very* conservative key lengths and well-respected
algorithms, and still have the encryption (or signature verification,
or whatever) taking only a small fraction of a second per message on
a low-end PC.
4. Often parts of cryptosystems are re-used for a different purpose to the
one the designer or specifiers originally intended, or the value of the
messages that are sent increases, or their value was underestimated in the
first place. It is more productive to design general purpose protocols,
algorithms, key management systems, etc., and to apply the limited amount
of available time and expertise of cryptanalysts on those relatively
few systems, than for every application writer to "roll their own" - and
it is a demonstrable fact that the results are usually more secure. (This
approach also has other advantages such as promoting interoperability
between applications.)
A general-purpose system must be capable of protecting data of very high
value and long lifespan, but it seems to be much easier to do this than
to design and analyse lots of application-specific systems independently.
5. Part of the value of crypto is determined by the trust that its user
base places in it. It's not sufficient for a system to be 'secure enough'
in the designer's opinion; it has to be *demonstrably* secure to the
satisfaction of its users (who, unless there is only one user, will have
different levels of paranoia or security awareness).
If you design a cryptosystem that is less secure than you could have
made it, you are asking for someone to point out, often loudly and
publically, that it is not secure enough for them - or even worse, to
claim that you deliberately weakened it.
For providers of cryptography who are:
- based in the U.S., and
- want to export their product, and
- are not prepared to jump through the hoop of printing out source and
getting it scanned overseas, or who have a closed-source product, and
- accept that their export market is going to be limited by the fact
that us foreigners are well aware that crypto that goes through the
current U.S. export process is weak,
there was possibly an argument for using crypto that is "not difficult".
But it looks as though even that argument might go away soon.
> My line is "The basic theory is to make a cryptosystem which can be
> applied with the least amount of effort but is impractical to break
> before the information becomes irrelevant using the currently available
> equipment."
As a general strategy this is a fundamentally bad idea. To summarise the
most important (IMHO) of the reasons above:
- You may overestimate how impractical the cryptosystem is to break. It
is very easy to do this unless you apply a generous safety margin,
paying particular attention to possible weak links.
- The amount of effort needed to make it impractical to *ever* break
the cryptosystem (at least by a cryptanalytic or brute-force attack)
is probably not much greater than the "least amount of effort" as
defined above.
> I need to source that, anyone know a web page, book, magazine article,
> etc which covers the above? I can't remember for anything where I saw
> that info.
I've noticed that there are far too many papers recently that decide
what the conclusion should be before doing any research. :-(
- --
David Hopwood <[EMAIL PROTECTED]>
PGP public key: http://www.users.zetnet.co.uk/hopwood/public.asc
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
"Attempts to control the use of encryption technology are wrong in principle,
unworkable in practice, and damaging to the long-term economic value of the
information networks." -- UK Labour Party pre-election policy document
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOF2qazkCAxeYt5gVAQF4kgf/U5QS9P8ZdnxM5UAA8f7RgwrhO0tHvR+z
IwMlPF3Lj47rY4A1xl9eljrnt97P/tLB7Fl4jtWvBDKCjP9menJMqlvqMefBF1jP
UULr099jH4Rj1WrcGqkybTknbSkkPzK4iktvVsc4rU+cFoRXDIInS7t2jUVsWlzG
qiNy7AGLHM9lTDPdL9zVo8neg+wZ0XXEyoZ2mhM1g729Bam4GMxRlqvxaWxbF8kP
ghG0/mFJKIclupKqiSj9fLpVYta7ZD0eEgxYqgjZwppr/ajkCuGgWTgCtECAOcby
qnQolfnrcYnn4o7PfVYin2Bd+BSGAf2am8yGbkn59TUPA6ZcdMhSqA==
=WFeP
=====END PGP SIGNATURE=====
------------------------------
** 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
******************************
