Cryptography-Digest Digest #730, Volume #9 Thu, 17 Jun 99 10:13:02 EDT
Contents:
A Thought or a Quoater ("rosi")
Re: Cracking DES ([EMAIL PROTECTED])
Re: Kryptos article ("Douglas A. Gwyn")
Re: CIA Enjoys a Challenge? ("Douglas A. Gwyn")
Re: DES and BPANN ("Douglas A. Gwyn")
Re: Simple Prime Number Question ("Douglas A. Gwyn")
Re: DES Encryption Function and an MLP ("Douglas A. Gwyn")
Re: OTP is it really ugly to use or not? (Dave Hazelwood)
Re: DES and BPANN ("Douglas A. Gwyn")
Simple Prime Number Question ([EMAIL PROTECTED])
test (Steve Droz)
Re: the student paradox (Nick Battle)
multiplicativ inverse (chciago)
Re: Phone scrambler : what encryption used ? ([EMAIL PROTECTED])
Re: multiplicativ inverse ([EMAIL PROTECTED])
Re: NIST annouces set of Elliptic Curves (DJohn37050)
newbie question (Sven Sprandel)
Re: test (Gergo Barany)
Re: DES Encryption Function and an MLP (fungus)
Re: Another free email? (Reuben Sumner)
Re: Simple Prime Number Question (Michael J. Fromberger)
just a quick check.. ("Matthew Bennett")
----------------------------------------------------------------------------
From: "rosi" <[EMAIL PROTECTED]>
Subject: A Thought or a Quoater
Date: Wed, 16 Jun 1999 23:17:46 -0400
Hi,
Preamble
As usual, not formal due to lack of mathematical training; there may be
spelling and grammar mistakes; things can be unclear; etc. etc.
I will use 'my style' but will follow conventions the best I can.
(Efficiencg is not the focus, practicality and security are)
Most or all of what I am to talk about may have already been treated
extensively in other literature. Apology in advance for any unintentional
repetition.
Four topics will be touched upon:
1. The 'basic' Needham-Schroeder (public-key) key establishment
2. The notion of key secure
3. The subtle difference between NP-hard and NP-complete
4. The possibility of making 'public' keys less public
2. and 3. are related in a certain way and may be dealt with together.
That's all for today.
Thank you very much.
--- (My Signature)
NOTES:
A quarter: not that I am hiding 3/4. The thought could very well be
incomplete.
I do not imply that I have solutions for any problems. My suggestion
is: we may be able to take a slightly different look at things.
Reason for using 'my style' (serious stuff treated lightly):
I am sure that many, like me, want to get some resolve out of IT (sorry),
even if we need to try wan moan tahm. I once wondered if I could suggest
a contest of the shortest explanation/description of what exactly IT is,
but was afraid. Not sure how the proposal might be taken. After I saw IT
resurfacing, I suddenly thought of one:
Any white cat is white & XOR preserves.
I first thought mine was pretty good, even though I was aware of a much
shorter one: un_encore_temp (see, poor English preserves well as well).
Finally, after some debate with myself, I seem to realize that the two
are 'equivalent at the abstract level', aware that 'XOR preserves' is
just too obvious and redundant. Congratulations!
(The definition of one-way in an informal manner)
So, the serious part: one-way and one-route are different things. In
essence, you can have multiple routes some or all of which are one-way.
It is not necessary that all different routes connect just two poits.
All could have one end connected to a single point, etc.
Defintion:
An active attack is one that affects the data communicated, exchanged,
stored, etc. by one or more parties in any fashion other than the designed,
intended, normal, routine manipulation of the data. E.g. holding them for
a while knowingly against the protocol design constitutes an active attack.
(You can attack your own communications if you are smart enough :)).
However, impersonation is viewed by me as a special type of attack,
even though it is normally regarded as an active attack. This is for
convenience rather than anything else.
--- End NOTES ---
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Cracking DES
Date: Thu, 17 Jun 1999 04:02:19 GMT
In article <7k683f$e1i$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (David Wagner) wrote:
> In article <7k5tfs$pui$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]>
> wrote:
> > Let us suppose that 2^73 bytes of memory is actually feasible. I
> > understand that for this attack to work we would need about 2^140
> > memory accesses.
>
> Not quite right; the naive MITM attack takes 2^73 bytes of memory
> and 2^70 memory accesses. A considerable improvement over exhaustive
> search, but still, as you say, not very practical due to the massive
> memory requirements.
Well, there is an even more naive implementation (the one I was
thinking of) that would just save 2^70 blocks indexed by the key and
require 2^140 memory accesses; if you index them by content (using a
hash table) and save both key and block then you get down to about 2^70
memory accesses. So, after all, it is meaningful to speak of 70 bits of
strength for 140 bit "Heavy-DES". In the same vain one can say that
Triple-DES with three different keys (a total of 168 bits) offers
"only" 112 bits of security against a MITM attack.
By the way, I understand that the DESX construct (pre- and post-
whitening) does defend against MITM attacks. So it seems that double-
DESX ( E(T) = k3 xor DES(k1, DES(k2, T xor k3)) ) is probably stronger
then triple-DES and is significantly faster.
> An improvement that drastically reduces the memory requirements
> (at some modest cost in computational complexity) is van Oorschot
> and Wiener's parallel collision search techniques. See e.g. their
> paper on breaking double-DES; I think it was in a recent CRYPTO.
I could not download this article (Parallel Collision Search with
Cryptanalytic Applications, Journal of Cryptology, volume 12.1) but the
abstract claims that double-DES offers 73 bits of security - not 56 - I
take it combining the cost of memory and time.
> > I think that the cryptanalytic community should agree on an attack
> > cost function that is more appropriate than just counting
> > encryptions. In an official comment to NIST I have proposed a
> > simple metric towards that end.
>
> Ooh! I agree: I think this is a very interesting research question.
>
> I wonder whether you can approximate the cost pretty well as a linear
> function of the resource requirements, at least for some resources.
> For instance,
> 1 MB of fast memory ~ 100 MB of slow memory
> ~ 2^36 trial encryptions / year ~ 1 KB of known plaintext
> (These are just examples, I don't know if they're reasonable
> estimates.)
In my comment I argue that the cost of known plaintext should grow
faster than linear.
> I'll look forward to reading your comment to NIST. Is it available?
You can find all public comments to NIST in:
http://csrc.nist.gov/encryption/aes/round1/comments/R1comments.pdf
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Kryptos article
Date: Thu, 17 Jun 1999 05:28:57 GMT
Jim Gillogly wrote:
> ... the last 97 characters:OBKR
> UOXOGHULBSOLIFBBWFLRVQQPRNGKSSO
> TWTQSJQSSEKZZWATJKLUDIAWINFBNYP
> VTTMZFPKWGDKZXTJCDIGKUHUAUEKCAR
> I think it is keyed rather than
> a OTP because ...
Notice its monographic IC is less
than 1, i.e. it is flatter than
uniform-random, but not so much
so that much significance can be
attributed to the fact. That
makes me suspect autokey, also.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: CIA Enjoys a Challenge?
Date: Thu, 17 Jun 1999 05:42:01 GMT
Jim Gillogly wrote:
> ... The sculpture is not on the standard "walk and gawk" tour of
> Washington...
That's quite an understatement. It was quite a coup when
I got access to Kryptos before my IC tickets came through.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: DES and BPANN
Date: Thu, 17 Jun 1999 05:32:40 GMT
"James Pate Williams, Jr." wrote:
> Do you know of any research in the open literature that applies
> various learning pardigms to DES?
Only the thesis that tried using a genetic algorithm.
(Not successful against DES.)
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Simple Prime Number Question
Date: Thu, 17 Jun 1999 06:00:15 GMT
[EMAIL PROTECTED] wrote:
> Fermat's (Little) Theorem: If p is a prime and if a is any integer,
> then a^p = a (mod p). In particular, if p does not divide a, then a^(p-
> 1) = 1 (mod p).
> If I choose a=10, p=3, 10^3=1000 and 10 mod 3 = 1, and 1000 != 1....
> And while you're at it, what is the definition of 1 mod n?
The whole equation is taken modulo n, bit just the right-hand-side.
i = j mod k means that (i - j) is exactly divisible by k.
This is "clock arithmetic" and is explained in any introduction to
number theory, such as Ore's book.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Crossposted-To: comp.ai.neural-nets
Subject: Re: DES Encryption Function and an MLP
Date: Thu, 17 Jun 1999 05:54:04 GMT
"James Pate Williams, Jr." wrote:
> Since the DES encryption function is a Boolean function (albeit a
> complicated one) of 64 inputs and 64 outputs can we safely assume
> that there exists a MLP with one hidden layer that given sufficient
> computation time, training examples, and hidden units can learn it
> with near perfect accuracy? If so, what training algorithm is to be
> suggested? Would the particle swarm optimization have a ghost of
> a chance of succeeding, if not, why?
What seems like eons ago, Keith Muller and I worked on cracking DES
as a Boolean function, but we assumed known plaintext, which should
be a very common situation, considering the small block size. The
complete system of equations took up just a few inches of fanfold
printer output, as I recall, which means it could easily be
represented within fast RAM in today's computers. But even with
known (constant) input and output, solving for the key is a very,
very, ..., very hard problem. I was working on it last year, but
lack of a financial sponsor caused my bosses to put me to work on
something else.
The real problem with trying to "converge" to solutions via
stochastic methods is that there is not a decent approximation
to continuity -- neighboring keys produce radically different
outputs and vice-versa. So one can never "get close" to a right
answer, which means that such algorithms just jump all over the
map.
------------------------------
From: [EMAIL PROTECTED] (Dave Hazelwood)
Subject: Re: OTP is it really ugly to use or not?
Date: Thu, 17 Jun 1999 04:34:26 GMT
By the "rught software" I mean software that makes OTP easier to use.
Software that automates creation and management of very good very
large pads and provides security for them as well.
And, does it in a way so that the pad becomes almost transparent to
the user.
I have some ideas about this and may produce such a software package
myself or work with someone who already has an otp package that can
be extended with such features.
sb5309 <[EMAIL PROTECTED]> wrote:
>What do you mean by the "right software" ?
>
>>
>>
>> I think OTP's are a lot more useful and secure than people
>> think and with 6 Gig disks costing a little more than $100
>> these days it means that with the right software you have a
>> very fast very secure solution for many applications.
>>
>
>
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: DES and BPANN
Date: Thu, 17 Jun 1999 05:34:04 GMT
Patrick Juola wrote:
> So you are of course correct that the statement ``NNs won't be
> successful at cryptanalyzing DES'' is merely a conjecture.
Actually it is much more than guesswork.
I already gave the essential argument.
------------------------------
From: [EMAIL PROTECTED]
Subject: Simple Prime Number Question
Date: Thu, 17 Jun 1999 04:50:03 GMT
Hi,
I'm trying to learn about prime numbers so I can generate some private
keys for public key encryption. I've found a great web site with a
good discussion of the subject of prime numbers
http://www.utm.edu/research/primes/prove/prove2.html#small
but I'm afraid I don't understand the following statement regarding
Fermat's little theorem:
Fermat's (Little) Theorem: If p is a prime and if a is any integer,
then a^p = a (mod p). In particular, if p does not divide a, then a^(p-
1) = 1 (mod p).
If I choose a=10, p=3, 10^3=1000 and 10 mod 3 = 1, and 1000 != 1....
but I'm sure there is something here that I'm misunderstanding; can
anyone explain where I'm going wrong?
And while you're at it, what is the definition of 1 mod n? The
discussion of strong probable primes uses 1 mod n in the discussion but
I don't know how to interpret it.
Thanks for any and all help,
Ron Bondy
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: Steve Droz <[EMAIL PROTECTED]>
Subject: test
Date: Thu, 17 Jun 1999 09:09:13 +0200
<!doctype html public "-//w3c//dtd html 4.0 transitional//en">
<html>
</html>
------------------------------
Date: Thu, 17 Jun 1999 09:35:10 +0100
From: Nick Battle <[EMAIL PROTECTED]>
Subject: Re: the student paradox
[EMAIL PROTECTED] wrote:
> So basically less knowledge = more ideas, more knowledge = worse
> ideas. One might argue that there are less ideas but they are higher
> quality, but one could also argue that more knowleege = more tools for
> ideas... :)
I once saw an interview with Sir Clive Sinclair (British inventor,
famous for building early calculators, digital watches, early personal
computers and the "C5" electric car). He said that when he gets
interested in a new field, he deliberately *avoids* the established
thinking in order to foster his own free thinking. The ideas then have
to be "brought down to Earth" before they can be realised of course (and
no doubt many fail), but the process of "guided ignorance" is an
interesting way of generating new ideas.
-nick
------------------------------
From: chciago <"gabriel. nock"@siemens.de>
Subject: multiplicativ inverse
Date: Thu, 17 Jun 1999 10:54:57 +0200
i want to implement IDEA, and i have to generate the multiplicativ
inverse of 2 16Bit integers...
i use the code of Bruce Schneiers code in applied cryptography, and this
code is standard, you find anywhere the same code, but in the function
mulInv, i get a division by zero, and i don't know why..
i stepped it a lot of times, but i can't find the problem, do you know
sth. like this??
is there anybody out there, who can help me ??
i don't know how to create the decryption keys.... and only by using the
already written code, it doesn't work.. great !!
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Phone scrambler : what encryption used ?
Date: Thu, 17 Jun 1999 11:28:50 GMT
In article <[EMAIL PROTECTED]>,
sb5309 <[EMAIL PROTECTED]> wrote:
> I don't know which one because as of now I am not concerned with a
> particular type. I am curious about the commonly used methods.
>
> May be you could drop some insights for me, whichever convenient.
Thanks
Well cordless phones (not cell phones) usually use very silly
encryption techniques (like xoring the audio with a binary counter).
So it does matter what phone you are talking about. I think you should
find out first.
The 'commonly used' methods would most likely be A5(and other A
methods), CMEA and ORYX.
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: multiplicativ inverse
Date: Thu, 17 Jun 1999 10:41:03 GMT
In article <[EMAIL PROTECTED]>,
chciago <"gabriel. nock"@siemens.de> wrote:
> i want to implement IDEA, and i have to generate the multiplicativ
> inverse of 2 16Bit integers...
>
> i use the code of Bruce Schneiers code in applied cryptography, and
this
> code is standard, you find anywhere the same code, but in the
function
> mulInv, i get a division by zero, and i don't know why..
> i stepped it a lot of times, but i can't find the problem, do you know
> sth. like this??
>
> is there anybody out there, who can help me ??
>
> i don't know how to create the decryption keys.... and only by using
the
> already written code, it doesn't work.. great !!
>
>
I have coded Euclid's extended algorithm used for
creating multiplicative inverses both for 16-bit and
32-bit register modes. E-mail me and I will send it
to you. This is written in assembly, so to use it in a
C program you will have to link it.
--
Robert G. Durnal
Web pages at www.afn.org/~afn21533
and members.tripod.com/~afn21533
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: NIST annouces set of Elliptic Curves
Date: 17 Jun 1999 12:37:29 GMT
These are curves which are approved for use by the US Federal Government to
protect their sensitive but unclassified data. This is an endorsement.
Also, the random curves should help alleviate some fears. I am sure all the
published curves will be studied.
And the random curves would present an interesting question to someone trying
to create a random weak curve. Namely, how prevalent can a (otherwise
unknown) "weak" curve be and still be found via a random seed? If it is too
rare, it is difficult to find using a seed, if it is too common, it will likely
be discovered by someone else.
Don Johnson
------------------------------
From: Sven Sprandel <[EMAIL PROTECTED]>
Subject: newbie question
Date: Thu, 17 Jun 1999 14:51:24 +0100
Hi,
I want to store pwd�s and a lizencekey in a database.
So I found the RSA - algorithm and implemented it in Active
Server pages. The problem is, that I get an overflow while
processing c^d ( even whith c=236 and d=299 !) .
ActiveServerPages does only support 8Byte datatyps.
So can anyone tell me how to solve this problem ?
What about larger c�s and d�s ? Is there any other
algorithm without such larger calculations ?
Thanks for any help.
Ceers, Sven
------------------------------
From: [EMAIL PROTECTED] (Gergo Barany)
Subject: Re: test
Date: 17 Jun 1999 12:30:50 GMT
In article <[EMAIL PROTECTED]>, Steve Droz wrote:
><!doctype html public "-//w3c//dtd html 4.0 transitional//en">
><html>
> </html>
You should use alt.test or similar groups for testing, and you should
*never* post HTML to a non-binary group.
Gergo
--
Simon's Law:
Everything put together sooner or later falls apart.
GU d- s:+ a--- C++>$ UL+++ P>++ L+++ E>++ W+ N++ o? K- w--- !O !M !V
PS+ PE+ Y+ PGP+ t* 5+ X- R>+ tv++ b+>+++ DI+ D+ G>++ e* h! !r !y+
------------------------------
From: fungus <[EMAIL PROTECTED]>
Crossposted-To: comp.ai.neural-nets
Subject: Re: DES Encryption Function and an MLP
Date: Thu, 17 Jun 1999 10:50:55 +0200
"Douglas A. Gwyn" wrote:
>
> What seems like eons ago, Keith Muller and I worked on cracking DES
> as a Boolean function
>
That was an interestign project. How much progress did you actually
make? Did you ever manage to solve DES for small number of rounds?
--
<\___/>
/ O O \
\_____/ FTB.
------------------------------
From: [EMAIL PROTECTED] (Reuben Sumner)
Subject: Re: Another free email?
Date: 13 Jun 1999 12:24:55 GMT
Reply-To: [EMAIL PROTECTED]
On Sat, 12 Jun 1999 19:43:06 GMT,
> [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote:
>Speaking of hushmail, has anyone heard of www.ynnmail.com? It's
>supposed to be free encrypted web mail, but I was wondering how secure
>it really is. I would appreciate any input on that from this forum.
Forget it. Looks like ordinary web mail with a SSL connection.
With hushmail, nobody should be able to read an email you send to me
except me (nobody means, not you, not hushmail, not my ISP, nobody but
me).
Hushmail is not perfect however (no authentication for instance).
If you are paranoid, use PGP (or GPG, also not perfect).
Reuben
------------------------------
From: Michael J. Fromberger <[EMAIL PROTECTED]>
Subject: Re: Simple Prime Number Question
Date: 17 Jun 1999 13:29:19 GMT
In <7k9upo$93a$[EMAIL PROTECTED]> [EMAIL PROTECTED] writes:
>
>I'm trying to learn about prime numbers so I can generate some
>private keys for public key encryption. I've found a great web site
>with a good discussion of the subject of prime numbers
>
>http://www.utm.edu/research/primes/prove/prove2.html#small
>
>but I'm afraid I don't understand the following statement regarding
>Fermat's little theorem:
>
>Fermat's (Little) Theorem: If p is a prime and if a is any integer,
>then a^p = a (mod p). In particular, if p does not divide a, then
>a^(p- 1) = 1 (mod p).
>
>If I choose a=10, p=3, 10^3=1000 and 10 mod 3 = 1, and 1000 != 1....
>but I'm sure there is something here that I'm misunderstanding; can
>anyone explain where I'm going wrong?
>
>And while you're at it, what is the definition of 1 mod n? The
>discussion of strong probable primes uses 1 mod n in the discussion
>but I don't know how to interpret it.
Hello there,
We say that "a is congruent to b (mod n)", if (a - b) is divisible by
n. In other words if a and b are some multiple of n apart, we
consider them to be "congruent" with respect to the modulus, n.
Congruency is typically denoted with an equivalence sign --
essentially a three-barred equal-sign. However, since I can't
reproduce that in text, I'll use '==' to mean "congruent", and '=' to
mean 'equals". If n divides (a - b), we write:
a == b (mod n)
You can think of 'x (mod n)' as being the set of all integers which
are congruent to x with respect to n. For computational purposes,
however, the one we're most concerned with is the smallest
non-negative integer which has this property -- and we can calculate
this by dividing x by n, and taking the remainder. For example:
25 == 8 (mod 17) (25 / 17 = 1, remainder 8)
5 == 5 (mod 9) (9 / 5 = 0, remainder 5)
Taking the smallest non-negative residue like this is known as modular
reduction.
Looking at your problem above, you've chosen a = 10 and p = 3.
Notice, however, that:
10 == 1 (mod 3)
It turns out that whether you do modular reduction before or after
computing the power gives you the same result:
10^3 = 1000 (note '=' is "equals", as you'd expect)
1000 == 1 (mod 3)
10 == 1 (mod 3)
1^3 = 1
1 == 1 (mod 3)
So, while 1000 does not _equal_ 1, it is _congruent_ to 1 with respect
to 3. This makes sense, since (1000 - 1) = 999, and 999 is clearly
divisible by 3 (3 * 333 = 999). And thus your example works as
expected.
I hope this helps!
Cheers,
-M
--
Michael J. Fromberger Software Engineer, Thayer School of Engineering
sting <at> linguist.dartmouth.edu http://www.dartmouth.edu/~sting/
gAX6a1S9+FfzQWW1RIqN6+H8lakJB3bZQbdI++c+3oqcqfiMdNFr3Bg1sfyeEdDHrrC/5dk3
Remove clothing if you wish to reply to this message via e-mail.
------------------------------
From: "Matthew Bennett" <[EMAIL PROTECTED]>
Subject: just a quick check..
Date: Thu, 17 Jun 1999 14:07:55 +0100
If I used SHA-1 to hash the 56-bit key used to encrypted file, and then
stored the hashed result in the same encrypted file, there shouldn't be a
security risk here?
Assuming the hashed number could easily be read from the file, since it is
only one-way there is no way you could obtain the original key from it? I'm
doing this to enable a program to check the right passphrase has been
entered by hashing it and comparing it to the hash stored in the file.
I'm considering this method over the check-phrase one simply because it
appears to be more convenient, since the user would only need to enter one
phrase, rather than two, to decrypt the file. Also, I assume the chances of
two different keys producing the same hashed result are so small so as to
make an incorrect key verification negligible?
Thanks,
/\/\/\//
------------------------------
** 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
******************************
