Cryptography-Digest Digest #931, Volume #11 Sat, 3 Jun 00 14:13:01 EDT
Contents:
Re: Pollard's algorithm for computing discrete logs (Mok-Kong Shen)
Re: Good ways to test. (Mok-Kong Shen)
Re: Cipher design a fading field? (Mok-Kong Shen)
Re: No-Key Encryption (Mok-Kong Shen)
Re: Cipher design a fading field? (Mok-Kong Shen)
Re: Good ways to test. (tomstd)
Re: Cipher design a fading field? (tomstd)
Re: Cipher design a fading field? (tomstd)
Need "attack time" measurements on a toy cipher... (long) ("TheGPFguy")
Re: Need "attack time" measurements on a toy cipher... (long) (tomstd)
Re: Need "attack time" measurements on a toy cipher... (long) ("TheGPFguy")
Re: Need "attack time" measurements on a toy cipher... (long) ("Scott Fluhrer")
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Pollard's algorithm for computing discrete logs
Date: Sat, 03 Jun 2000 19:19:10 +0200
Pollard in his original paper also introduced another method with
some association to kangaroo but his description of that was rather
unclear, if I don't err. Does anyone happen to have better
literature on that?
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Good ways to test.
Date: Sat, 03 Jun 2000 19:19:04 +0200
tomstd wrote:
> >> From a medical point of view it's similar. If 5% of the
> people
> >> get sick with brand A, and only 0.01% with brand B, well we
> >> would pick brand B. But that doesn't mean in the long run
> brand
> >> B is any better. Just over that short period of analysis.
> >
> >There is nothing parallel to the above in crypto. You may
> continue
> >to use a cipher without knowing that it has been cracked by some
> >mighty opponents. What one can often do is to go conservative,
> >e.g. using superencipherment, in the hope that the risk is
> somewhat
> >reduced. But there can be no absolute assurance.
>
> Again I disagree. You could be using Tylenol for a century not
> knowing that it has side effects.
I have difficulty in comprehending what you are driving at with the
above sentences. Let me point out
1. I was claiming that the sort of numerical figures, like 5% and
0.01% in your example, do not have parallels when considering
strength of crypto algorithms. It follows that it is not possible to
use that example as an analogy.
2. I know too little about chemistry or phamacology to know what
substance you mentioned is. But apparently you were referring to
the issue of the yet unknown side effects of drugs. Yes, this does
seem to have analogy in crypto, namely the yet unknown
(not yet existing or already existing but secret) techniques of attack.
To that point all what I can say is to repeat my conviction that
anyone applying crypto is responsible to himself for the consequence
of what algorithm he chooses and how the whole security system is
organized and run. No other person can carry that responsibility
for him. He can gather all relevant informations that he can manage
to obtain. But he has to make his own decision (including such as
to blindly and totally rely on what a certain guru says) and has no
one but himself to blame, if that decision happens to turn out to
be wrong.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Cipher design a fading field?
Date: Sat, 03 Jun 2000 19:18:56 +0200
Jack wrote:
> You can be assurred that phony
> crypto gods will say we need more speed in encryption rates. I
> say let the hardware speed improve but with just faster methods
> being proposed I feel it makes us the people more vulnerable to
> a evil big brother.
There is definitely some truth in what you said. The 'one thing fits all'
stategy, requiring algorithms for encrypting top-level secrets to also
satisfy the tight memory requirements of some less critical applications,
and the psychologically seducing advocation for getting ever higher
performance combine to set sort of implicit upper bound of the
strength of algorithms that the current state of the art is able to
produce. That upper bound might not be ideal for applications of
highest security level.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: No-Key Encryption
Date: Sat, 03 Jun 2000 19:19:14 +0200
John Savard write:
> <[EMAIL PROTECTED]> wrote, in part:
>
> >I am not yet convinced of that. Since '*' is assumed to be associative,
> >we certainly have M*(A*B)=M*(B*A). If this is true for any M, I
> >think that by applying the inverse one should have A*B=B*A, which
> >is the commutativity. What is the flaw here?
>
> It's true that there is a right-inverse, so that from M*A, we can
> obtain M by doing (M*A)/A. But I don't recall seeing it stated that a
> left-inverse exists.
>
I suppose you allow a bit more discussion. From the expression like
M*A*B it can be implied that M, A and B are from the same domain.
Hence the type of operands on both sides of the operator '*' are
the same. Now, assuming the existence of a right inverse, we get
I=A/A, the identity. Substituting I for M in the general equation
M*A*B=M*B*A results in I*A*B=I*B*A and hence A*B=B*A
on applying associativity. Could you see any flaw in the above?
Thanks.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Cipher design a fading field?
Date: Sat, 03 Jun 2000 19:27:00 +0200
tomstd wrote:
> To quite the contrary the AES ciphers are faster and more secure
> then DES. So your idea of fast != secure is invalid.
There are more issues involved than is apparent. One has also to
take technological advances into consideration. A modern airplane
is, for example, considerably more secure than a vessel of the 18th
century.
M. K. Shen
------------------------------
Subject: Re: Good ways to test.
From: tomstd <[EMAIL PROTECTED]>
Date: Sat, 03 Jun 2000 10:17:17 -0700
In article <[EMAIL PROTECTED]>, Mok-Kong Shen <mok-
[EMAIL PROTECTED]> wrote:
>
>
>tomstd wrote:
>
>> >> From a medical point of view it's similar. If 5% of the
>> people
>> >> get sick with brand A, and only 0.01% with brand B, well we
>> >> would pick brand B. But that doesn't mean in the long run
>> brand
>> >> B is any better. Just over that short period of analysis.
>> >
>> >There is nothing parallel to the above in crypto. You may
>> continue
>> >to use a cipher without knowing that it has been cracked by
some
>> >mighty opponents. What one can often do is to go
conservative,
>> >e.g. using superencipherment, in the hope that the risk is
>> somewhat
>> >reduced. But there can be no absolute assurance.
>>
>> Again I disagree. You could be using Tylenol for a century
not
>> knowing that it has side effects.
>
>I have difficulty in comprehending what you are driving at with
the
>above sentences. Let me point out
>
>1. I was claiming that the sort of numerical figures, like 5%
and
> 0.01% in your example, do not have parallels when
considering
> strength of crypto algorithms. It follows that it is not
possible to
> use that example as an analogy.
You are missing the picture.
Crypto: I can say a block cipher has 'X' resistance to 'Y'
attacks.
Medicine: I can say 'X' people get better and 'Y' people get
dead.
Same thing. In crypto I can say 'DES has a resistance to linear
attacks effectively of O(2^43) work' making it 'strong'. In
medicine I can say 99.99% people got better but 0.01% died
making it 'a cure'.
We didn't know (or now either) if DES could have been broken
easily, same for medicine. Those 0.01% may have had kids before
they died that have some wierd genetic disease making 0.01%
become much larger.
That's why I called it comparative. You wouldn't use FEAL-8
over Blowfish would you? Why because given all that we know
Blowfish is more secure. Is that definative? Not a shot in
hell. But it's better then "What cipher will I use today?".
>2. I know too little about chemistry or phamacology to know
what
> substance you mentioned is. But apparently you were
referring to
> the issue of the yet unknown side effects of drugs. Yes,
this does
> seem to have analogy in crypto, namely the yet unknown
> (not yet existing or already existing but secret)
techniques of attack.
> To that point all what I can say is to repeat my
conviction that
> anyone applying crypto is responsible to himself for the
consequence
> of what algorithm he chooses and how the whole security
system is
> organized and run. No other person can carry that
responsibility
> for him. He can gather all relevant informations that he
can manage
> to obtain. But he has to make his own decision (including
such as
> to blindly and totally rely on what a certain guru says)
and has no
> one but himself to blame, if that decision happens to turn
out to
> be wrong.
>
You're right. Companies like Entrust and RSA are *liable* for
any damages that occur when people use their tools. So I would
assume they are doing the best they can.
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
Subject: Re: Cipher design a fading field?
From: tomstd <[EMAIL PROTECTED]>
Date: Sat, 03 Jun 2000 10:19:24 -0700
In article <[EMAIL PROTECTED]>, Mok-Kong Shen <mok-
[EMAIL PROTECTED]> wrote:
>
>
>Jack wrote:
>
>> You can be assurred that phony
>> crypto gods will say we need more speed in encryption rates. I
>> say let the hardware speed improve but with just faster
methods
>> being proposed I feel it makes us the people more vulnerable
to
>> a evil big brother.
>
>There is definitely some truth in what you said. The 'one thing
fits all'
>stategy, requiring algorithms for encrypting top-level secrets
to also
>satisfy the tight memory requirements of some less critical
applications,
>and the psychologically seducing advocation for getting ever
higher
>performance combine to set sort of implicit upper bound of the
>strength of algorithms that the current state of the art is
able to
>produce. That upper bound might not be ideal for applications of
>highest security level.
This makes no sense.
While yea we can make 1000 round ciphers that are secure,
wouldn't the more intelligent thing be to make 10 round ciphers
that are just as secure?
I agree that you should be conservative (i.e Serpent, Rijndael-
18, RC6-24) but not out of proportion.
I strongly believe that Twofish is the best counterexample to
your point. It's appears strong yet performs well in a variety
of platforms. Does that interoperability make it a bad cipher?
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
Subject: Re: Cipher design a fading field?
From: tomstd <[EMAIL PROTECTED]>
Date: Sat, 03 Jun 2000 10:21:06 -0700
In article <[EMAIL PROTECTED]>, Mok-Kong Shen <mok-
[EMAIL PROTECTED]> wrote:
>
>
>tomstd wrote:
>
>> To quite the contrary the AES ciphers are faster and more
secure
>> then DES. So your idea of fast != secure is invalid.
>
>There are more issues involved than is apparent. One has also to
>take technological advances into consideration. A modern
airplane
>is, for example, considerably more secure than a vessel of the
18th
>century.
I am failing to see the point? Does my K6-2 make 3DES any less
secure? Is that your point?
The whole AES contest is based on *new* cipher designs. Like
Serpent for example is based on the bitsliced implementation of
sboxes, developped originally to speed up DES. This is called
progress.
I don't see how Good performance on a 6805 will make the cipher
any less secure.
Tom
* 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: "TheGPFguy" <[EMAIL PROTECTED]>
Subject: Need "attack time" measurements on a toy cipher... (long)
Date: Sat, 03 Jun 2000 17:38:21 GMT
Hi, folks.
I'm a software developer working for a fairly large client. They want =
to store some parameters of low-to-medium sensitivity on a network drive =
in enciphered form. My direct management doesn't want to spend any time =
implementing a real cipher, so I built a toy one. Please, let's not =
spawn a thread about why they should use a real cipher, I already know =
the reasons. I'm moderately versed in implementing cryptography, but =
not at ALL versed in cryptanalysis.
What I'd like to know is how long it *actually* takes to crack the =
simple cipher shown below.
Any takers? =20
Here are the details:
1. This is a known ciphertext, unknown plaintext attack.
2. All of the data were enciphered with the SAME KEY.
3. The key length is longer than any of the enciphered data.
4. The key was generated with an INSECURE random number generator.
(It's probably a linear congruential generator.)
5. Attack by any method you choose. Show the plaintext of each =
parameter you successfully retrieve. All parameter's plaintext are =
printable ASCII. If you can also retrieve the key, show it as well (as =
a set of hex pairs, i.e. A5 FF 02 7B...).
6. Clearly describe the attack you used.
7. IMPORTANT: Time Yourself. Include any time you spend in writing =
code. I'm trying to find out how fast the initial attack is, not =
repeated attacks once compromised.
8. Please post the results in this newsgroup.
[The background reasons for all this are: (a) I know how long a =
knowledgeable programmer will take to find the secured copy of the =
application; (b) I know how long it will take him/her to retrieve the =
parameters by running the app in a debugger; (c) I know how long it will =
take to then misuse those parameters. This toy encipherment only has to =
delay a cryptanalyst the same amount of time as a+b+c.]
THE ALGORITHM (a toy cipher -- given in encipher order, reverse to =
decipher)
1. Compute the length of the ASCII plaintext. Encode this length as a =
single ASCII character. (The length therefore is limited to 255 or =
less.)
2. Prefix the plaintext with this ASCII character.
3. Prefix the result with an additional 6 chars of random garbage data. =
(Remember, I'm using an insecure PRNG.)
4. Append to the result, 4 - 40 chars of random garbage data, to =
obscure the plaintext length.
(When deciphering, the receiver will use the length character (from =
steps 1-2) to know where the real data stops and this garbage data =
starts.)
5. Iterate across this padded plaintext "P". The ciphertext is "C" =
and the key is "K".
a. TempChar =3D (P[i] + C[i-1]) mod 256
b. C[i] =3D (TempChar + K[i]) mod 256
At the beginning of the loop, set TempChar =3D P[0].
* * *
SAMPLE DATA
This is binary octet data shown as ASCII hex pairs. The hex pairs are =
(obviously) all run together. The bracketed headings are just random =
ID's to separate each pair of parameters. This format is readable by a =
variety of parsers including the INI functions in the Micro[cough!] =
Win32 API.
[MBAZ]
PARM1=3D21E9C63A63159BF28A3B17D71291105E7988824A39FF504DA27EC10798A7FA325=
ACB9794A838D8A30A67E855
PARM2=3D33582DFADF72006C11D0AAB485F5FB76C497EA182A250C38593E301EB6F93E07A=
8002DBDC48A84247BEB32EE13
[MBAB]
PARM1=3DBE27EF66A8941A7109BA7E45B8557C3952F9414BE87D009C9F3AD5F1412900464=
64697E4D1A9CCEE3E6F5C3905122D3C62DF89
PARM2=3DAD792A2E50A12F852ADCB7CFA010168EDCAF02F964E3A229
[MBAE]
PARM1=3DE5A9547CA376FC53EB9C634C8678D06C43FCDDBCBF5E15625229F8AADD6A19A06=
12EFAEF5781A0A8F7EA7DB31A8E6D3D29
PARM2=3D5FDE9FB05025B316B67309E2B3212AAF07DA5A53C2265776EA9949F5651BAE5EF=
32459CC8D6F6E612BC2A7082D
[MCAB]
PARM1=3DE92EE360C2A52C831BCC90A6204D114E5EF97AB2339604CE7E82D66E6994CDFC7=
526F0DF663B
PARM2=3DD1A5D2B641F987E8974A0D25F6666CE4320556709B470FEA83F73C043D52D10D5=
94673F0C154C6FBFC
[MCAZ]
PARM1=3D5EBE7B38AB51D82FC778546A73FA7784FC1AEB2D
PARM2=3D38C37A0C61800E680DC097A374E4EA65B386D7DC6673F17ED5535624
[MLAB]
PARM1=3D9172928B1BFE84DB7324E8DE6E19E5030AF95F07EDF2
PARM2=3D1A2775893CD462C37225E800D14147BF0DE031AA477B36F93531FF9ED3A545D3D=
5F9C976307E106B273E1BAFCCE06A44
[MXAZ]
PARM1=3DDE451D9C2BF077CE6617F309E89563511A0B8D06EC578687A0AAE5BFE3662BE84=
3E097B0D41787FEFF
PARM2=3D7B608583B0D05EB84F17DCFECF3F45C00EE12F6378DE261257335EA56295E54F2=
1C797D568
[MUAZ]
PARM1=3D755BEE1023E66DC45C0DE9FFB4427A34AF6E5B0C31
PARM2=3D2FA3003E83FF86DD75260218A130E1A3C907E768C8B201F425D3E652A76B554F2=
534FF3401D6
[MOAB]
PARM1=3DF4C2AABCF0DD63BA5203C7812B30347F8B4360
PARM2=3D9FDF820CFDF583E38E4A0D25F6666CE43205542F1A8757BBA38434C7965CC3467=
056842961720C51CA834078C6208C8E48CD5AB8EB45D6ABC574F1
[MOAZ]
PARM1=3DAB11098B9856DD34CC7D596F084DE09E87A28D5F7B2E8F16
PARM2=3D292C4224319927953AF9BEE0B12127A2F0C312B4750E2CDF11
[MXAB]
PARM1=3D61834B7BD3C54BA23AEBAF2940B5E66C63556D9627959C18BB11D761864FF358F=
6E57D2F972EDF4AD6B6FCE8E891542E
PARM2=3DD78616F2F1D361C26D1FF810E15157CF1DF03E314B9185CAF7B98CE6FF95DC0CA=
AF5D3D526EA78738EECC3DAFF
* * *
Thanks a bunch in advance!
Have fun cracking!!
------------------------------
Subject: Re: Need "attack time" measurements on a toy cipher... (long)
From: tomstd <[EMAIL PROTECTED]>
Date: Sat, 03 Jun 2000 10:44:38 -0700
It looks awefully like a Vinegere cipher.
If you know the reasons for using better cipher and choose not
to you are being stupid, and so is your boss.
Heck even XTEA is better then nothing and takes 3 seconds to
implement.
Tom
* 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: "TheGPFguy" <[EMAIL PROTECTED]>
Subject: Re: Need "attack time" measurements on a toy cipher... (long)
Date: Sat, 03 Jun 2000 18:08:21 GMT
tomstd <[EMAIL PROTECTED]> wrote in article =
<[EMAIL PROTECTED]>...
> It looks awefully like a Vinegere cipher.
Yup.
>=20
> If you know the reasons for using better cipher and choose not
> to you are being stupid, and so is your boss.
"No" and "Yes" respectively. =20
I'm going to tuck away this example in my briefcase and pull it out =
every time someone says "oh, we don't need anything really secure." My =
standard statement is "this won't keep a knowledgable cryptanalyst out =
of your data for any length of time whatsoever." The standard response =
query seems to be "well, how long is THAT?" Right now I don't really =
know if it's 5 minutes or 20.
Also, they don't have any good solution to the key management problem, =
so it really doesn't need to be any stronger than a couple hour's =
wall-time delay.
>=20
> Heck even XTEA is better then nothing and takes 3 seconds to
> implement.
>=20
Okay... I hereby downgrade my statement in my first message to "...I'm =
*mildly* versed in implementing crypto."
:-)
What's XTEA?
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Need "attack time" measurements on a toy cipher... (long)
Date: Sat, 3 Jun 2000 10:54:30 -0700
TheGPFguy <[EMAIL PROTECTED]> wrote in message
news:01bfcd82$7497a100$[EMAIL PROTECTED]...
>I'm a software developer working for a fairly large client. They want to
store some
>parameters of low-to-medium sensitivity on a network drive in enciphered
form.
>My direct management doesn't want to spend any time implementing a real
cipher,
>so I built a toy one. Please, let's not spawn a thread about why they
should use a
>real cipher, I already know the reasons. I'm moderately versed in
implementing
>cryptography, but not at ALL versed in cryptanalysis.
Stupid question: why don't you go on the Web, and get a pre-written version
of DES or TwoFish or some other well known generally accepted cipher. It
should take *less* time to use that than to write up and test your home-brew
cipher, and will almost certainly be more secure.
And, if you think your direct management is so stupid [1] to berate you for
not spending the additional time developing your weaker version, don't tell
them.
>Here are the details:
>1. This is a known ciphertext, unknown plaintext attack.
>2. All of the data were enciphered with the SAME KEY.
>3. The key length is longer than any of the enciphered data.
>4. The key was generated with an INSECURE random number generator.
> (It's probably a linear congruential generator.)
BTW: I'd spend the time you saved fixing up the key generator. Weak key
generation is a much greater weakness than a vaguely bad block cipher, and
unless you fix up both weaknesses, the entire system is pretty much
worthless.
[1] And I do mean stupid: your boss should only care that the project be
done, and in this particular case, re-using the work of others is both
faster (== cheaper) for you, and gives a better (more secure, but fix that
key generation) result. Any boss that doesn't like that meets my definition
of "stupid"
--
poncho
------------------------------
** 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
******************************
