Cryptography-Digest Digest #946, Volume #12 Tue, 17 Oct 00 18:13:00 EDT
Contents:
Re: A question about DES ("Joseph Ashwood")
Re: Works the md5 hash also for large datafiles (4GB) ? (Paul Schlyter)
Re: Looking for small implementation of an asymmetric encryption algorithm ("Joseph
Ashwood")
Re: SALT + stream cipher (Simon Johnson)
Re: Looking for small implementation of an asymmetric encryption (John Myre)
Re: Looking for small implementation of an asymmetric encryption (John Myre)
Re: Works the md5 hash also for large datafiles (4GB) ? (John Myre)
Re: the cipher challenge cracked ... (Sundial Services)
Re: SALT + stream cipher (John Myre)
Re: x509 (Doug Stell)
Re: Looking for small implementation of an asymmetric encryption ("j0n.walker")
Re: pseudo random test (=?ISO-8859-1?Q?Jacques_Th=E9riault?=)
Re: Basic skills and equipment... (Scott Craver)
Re: Smartcard, Mathematical Proof? (David Schwartz)
Re: "The code book" where (JPeschel)
Re: SALT + stream cipher (Tom St Denis)
Re: A new paper claiming P=NP (Eric Lehman)
----------------------------------------------------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: A question about DES
Date: Tue, 17 Oct 2000 12:05:12 -0700
> I'm an italian computer science student and I'm a beginner in
cryptography.
> I've the following question: what's the reason 'cause, in last DES step,
> they applied the inverse of the initial permutation to the 64 bit block
> instead of a different kind of permutation ?
Because they felt like it. It serves a very minor purpose making everything
feel rounder. there is no cryptographic reason for it, just as there would
be no reason for another kind of (unkeyed) permutation.
Joe
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: Works the md5 hash also for large datafiles (4GB) ?
Date: 17 Oct 2000 20:36:54 +0200
In article <8sh0bg$38v$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
> I have to compare diskimages. To save diskspace I want to use
> a hash (md5).
>
> Work md5 for such large files?
> I know I would generate a 128bit signature, what I mean is, is
> the probability that two different large files have the same
> signature as low as for smaller files.
>
> In other words, is the algorthm of md5 only designed for "small"
> files?
No - the md5 algorithm is designed for files or other data structures
of any size greater than zero, including extremely large sizes. For
really big data structures you chop up your data into manageable
pieces (for a disk image e.g. one disk track at a time), and then
feed one chop at a time to md5.
In the reference C implementation you do MD5 like this:
MD5_Init once at the beginning
MD5_Update any number of times, but at least once
MD5_Final compute the final MD5 hash
In all cases the risk for a hash collision will be very small,
or one out of 2^128 (= approx one ut of 3.4E+38). Which means
if you generate one hash, and then all people on the Earth
generates one billion new hashes each, every second 24 hrs/day,
you can expect a collision with your first hash to occur after
approximately 16 billion billion years !
So don't worry about hash collisions.
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: pausch at saaf dot se or paul.schlyter at ausys dot se
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Looking for small implementation of an asymmetric encryption algorithm
Date: Tue, 17 Oct 2000 12:21:02 -0700
Probably your best bet would be to go with ECC or XTR, they at least use
smaller keys than the others. You'll also find that those general purpose
libraries tend to use the most powerful algorithms available, instead of the
most space efficient. You may need to hand-code the system to get what you
need. One possible proposal is to usee ECC-DH (ECC for key negotiation), use
the negotiated value as a key for Rijndael, or Skipjack, either of those
should be small enough for even the tightest environment (Skipjack is
smaller but slower). If you have a fast exponentiator available (depends on
your embedded enivironment) you might still want to use RSA (the bloat from
the DH/ElGamal values would be too much), and eliminate the
Rijndael/Skipjack phase. Depending on what you need there are various people
on this group that can consult, either for free (generally reserved for
Academia) or for a fee (for profit).
Joe
<[EMAIL PROTECTED]> wrote in message news:8si75d$3qd$[EMAIL PROTECTED]...
> Hello,
>
> I'm looking for a small implementation of an asymmetric encryption
> algorithm suitable for a low-memory embedded system. I need to encrypt
> short (<64 bits) fixed-length messages. Decryption will take place on a
> much more capable system. Most of the source code I've found is very big
> and includes generic libraries for doing things like bignum math. Before
> I try to whittle those down to just the pieces I need I thought I'd ask
> here first.
>
> Thanks in advance,
> Emery
>
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
------------------------------
From: Simon Johnson <[EMAIL PROTECTED]>
Subject: Re: SALT + stream cipher
Date: Tue, 17 Oct 2000 19:20:06 GMT
In article <#XzYgTGOAHA.324@cpmsnbbsa09>,
"Joseph Ashwood" <[EMAIL PROTECTED]> wrote:
>
> "William A. McKee" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > When you encrypt a file with a stream cipher, you choose a password
and
> salt
> > (random number) to seed the pseudo random number generator. Then
you xor
> > the file with the output from the PRNG. My question is how do you
> remember
> > the salt? Do have to keep it secret or can you save it as the
first few
> > bytes of the encrypted file?
> Just to answer the question, you could broadcast the Salt
(initialization
> vector) on the local news, spray paint it on the side of a building,
and put
> it at the front of the encrypted file.
>
> Now about Toms comment to use a hash, that's up to you, there are
certainly
> at least two sides the argument. First, the hash cannot increase the
entropy
> of the salt+passphrase, and since it can decrease it, it shouldn't be
used.
> The second side, and the (IMNSHO) more reasonable side is, even if the
> stream cipher is broken, if you used a hash the attacker cannot
recover your
> passphrase, besides the likelihood of loss of entropy in a hash like
SHA-1
> is trivial until you reach at least 80 characters, it's safe to
disregard
> it, with SHA-256 it's around 128 characters.
> Joe
>
>
A decrease in entropy can occur in an hashing algorithm? Is this true,
can you present a logical argument for this?
--
Hi, i'm the signuture virus,
help me spread by copying me into Signiture File
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Looking for small implementation of an asymmetric encryption
Date: Tue, 17 Oct 2000 13:43:26 -0600
[EMAIL PROTECTED] wrote:
<snip>
> I'm looking for a small implementation of an asymmetric encryption
> algorithm suitable for a low-memory embedded system. I need to encrypt
> short (<64 bits) fixed-length messages. Decryption will take place on a
> much more capable system.
<snip>
"It depends."
It isn't really true that your basic requirement is to
encrypt your messages. Your real requirements have to do
with what information needs to be kept private, what it
is worth, what your potential attackers can do, and so on.
Also, you may need secrecy, or authentication, or both.
There are a lot of variations.
For instance, is the low-memory embedded system intended
to be left alone? Could an attacker grab one and learn
everything stored in it? Does it have to run without
help, or would someone (authorized) "log in", as it were?
The best solution always comes from realizing your exact
requirements, avoiding preconceptions.
JM
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Looking for small implementation of an asymmetric encryption
Date: Tue, 17 Oct 2000 13:51:02 -0600
Joseph Ashwood wrote:
<snip>
> One possible proposal is to usee ECC-DH (ECC for key negotiation), use
> the negotiated value as a key for Rijndael, or Skipjack, either of those
> should be small enough for even the tightest environment (Skipjack is
> smaller but slower).
<snip>
Note that he specified <64 bit messages. You'll have to
modify a few things to get the above proposal to work.
Why he asked for an asymmetric algorithm I don't know;
maybe he has a good reason or maybe not.
Also, we don't know if DH is actually appropriate; maybe
the MITM attack is a real concern.
JM
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Works the md5 hash also for large datafiles (4GB) ?
Date: Tue, 17 Oct 2000 13:56:51 -0600
Paul Schlyter wrote:
<snip>
> No - the md5 algorithm is designed for files or other data structures
> of any size greater than zero, including extremely large sizes.
<snip>
Actually, isn't the algorithm well defined even for zero input?
I think any number of bits works, up to 2^64 - 1.
(Not that I'd trust an implementation to get it right without
checking; and few implementations allow input other than sequences
of 8-bit bytes.)
JM
------------------------------
Date: Tue, 17 Oct 2000 13:04:47 -0700
From: Sundial Services <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: the cipher challenge cracked ...
It is quite interesting indeed that Simon Singh's cipher challenge,
which consisted of ten historical ciphers (including AES and DES) and
was slated to run for 10 years with a prize of 10,000 pounds ... was
solved in very-slightly more than one year.
It's also quite revealing that the DES portion of the cipher was solved
in eight hours, "by throwing a computer at it."
==================================================================
Sundial Services :: Scottsdale, AZ (USA) :: (480) 946-8259
mailto:[EMAIL PROTECTED] (PGP public key available.)
> Fast(!), automatic table-repair with two clicks of the mouse!
> ChimneySweep(R): "Click click, it's fixed!" {tm}
> http://www.sundialservices.com/products/chimneysweep
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: SALT + stream cipher
Date: Tue, 17 Oct 2000 14:02:18 -0600
Simon Johnson wrote:
<snip>
> A decrease in entropy can occur in an hashing algorithm? Is this true,
> can you present a logical argument for this?
<snip>
The output is some fixed size; the input could be larger; and
the input could (conceivably) have full entropy. Q.E.D.
This is presumably a theoretical rather than practical
restriction, as passphrases practically never have more
entropy than the hash size.
JM
------------------------------
From: [EMAIL PROTECTED] (Doug Stell)
Subject: Re: x509
Date: Tue, 17 Oct 2000 20:09:30 GMT
On Tue, 17 Oct 2000 11:29:26 +0200, "Antonio Merlo"
<[EMAIL PROTECTED]> wrote:
The algorithmIdentifier is duplicated and included in the signed data
of the certificate, because the one in the signature is not protected,
i.e., included in the signed data. This is intentional.
>x509 certificate has the following syntax:
>
>Certificate ::= SIGNED { SEQUENCE {
> version [0] Version DEFAULT v1,
> serialNumber CertificateSerialNumber,
> signature AlgorithmIdentifier,
> issuer Name,
> validity Validity,
> subject Name,
> subjectPublicKeyInfo SubjectPublicKeyInfo,
> issuerUniqueIdentifier [1] IMPLICIT UniqueIdentifier OPTIONAL,
> subjectUniqueIdentifier [2] IMPLICIT UniqueIdentifier OPTIONAL
> extensions [3] Extensions OPTIONAL
>}
>
>
>where signed mean:
>
>SIGNED { ToBeSigned } ::= SEQUENCE {
>toBeSigned ToBeSigned,
>COMPONENTS OF SIGNATURE { ToBeSigned }}
>
>SIGNATURE { ToBeSigned } ::= SEQUENCE {
>algorithmIdentifier AlgorithmIdentifier,
>encrypted ENCRYPTED-HASH { ToBeSigned }}
>
>
>
>Does anybody know why it is included algorithmIdentifier on the certificate
>date if it is present on data signature? Currently this information is
>duplicated on all certificates and I don't know why?
>
>
>
------------------------------
From: "j0n.walker" <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Looking for small implementation of an asymmetric encryption
Date: Tue, 17 Oct 2000 21:44:09 +0100
Hi, I'm also looking for (any) cipher method for an embedded system, but my
requirements are simpler:-
Need to store a 10 digit password(number) in some encypted form (2.5 16 bit
words) as an encypted value.
All the code has to be written in assembler of an ancient vintage (the
number system is in octal!).
The user will then type his 10 digit passnumber, the number will be
processed using the algorithm and finally compared against the stored value.
As with most systems, knowlege of the algorithm shouldn't make it much
easier to break, although the code will be protected from prying eyes.
Knowledge of the password isn't the end of the world but I would like to
make it more difficult than the current system which just multiplies each 4
bits by a different constant and sums each group of 4 to form a 16 bit
result.
I realise that with only 40 bits it's probably close to being trivial but
hope springs eternal.
I've scanned the web discussion groups but password security doesn't seem to
get discussed to much at least not in the terms of above.
[EMAIL PROTECTED]
------------------------------
Subject: Re: pseudo random test
From: [EMAIL PROTECTED] (=?ISO-8859-1?Q?Jacques_Th=E9riault?=)
Date: Tue, 17 Oct 2000 21:15:24 GMT
Tim Tyler <[EMAIL PROTECTED]> wrote:
>
> Posting binary data to non-binary usenet groups is liable to get you
> lynched.
>
I didn't realized that this news group was you property or that you were
the sci.crypt POLICEMAN....
I regret that the post was made...I will try to live with that for the
rest of my life.
Please don't do any harm to my children for I have sin in good faith.
Again, please forgive me...
Jacques Th�riault
------------------------------
From: [EMAIL PROTECTED] (Scott Craver)
Subject: Re: Basic skills and equipment...
Date: 17 Oct 2000 21:03:17 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
>[EMAIL PROTECTED] (Scott Craver) wrote:
>>
>> Asking what math background is relevant to crypto is
>> off topic for sci.crypt??!!
>>
>> Of course, his question was perfectly on-topic, and without
>> your retorts the rest of the thread would be on-topic too.
>
>Ok obviously you guys are just waiting to flame me at every chance.
It happens naturally, honestly.
> I think if you want to get into crypto-math you should know very basic
> terms like "ciphertext" or "salt". Otherwise what's the point?
Here's a tiny little thought: maybe the original poster,
who is now into crypto and looking for more in-depth stuff
like what math background is necessary, probably already
knows what "ciphertext" is.
>Of course this concept of actually knowing what you're talking about
>eludes most of you here (and me sometimes).
It's sentences like this, I think, that cause people to pour
molten lava on you. Do you not see why comments like this would
trigger people to flame you back? Do you see why you shouldn't
say that to people some of whom have years more education on
in the field, and have published useful results as proof?
>Either way you still need to know crypto vocabulary. So I don't see
>where Bob get's off telling me my "read the faq, some good intros,
>etc..." is off-course.
Well, the original poster did ask 3 questions, and your
answer could be relevant to the second one. I only
responded because of your silly defense that discussions
of math are off-topic for crypto. Discussions of
factoring algorithms, for instance, are very much on topic
even if nobody ever says "ciphertext" or "plaintext."
>Tom
-S
------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: Smartcard, Mathematical Proof?
Date: Tue, 17 Oct 2000 14:15:14 -0700
Mykhailo Lyubich wrote:
> I mean the following:
> There are two client systems, S1 and S2, the architectures of which
> are different. The both systems are the implementation of a
> communication protocol. The system S1 is simple implementation of this
> protocol. On the other hand, system S2 uses a chipcard to construct some
> parts of the exchanged messages inside the chipcard.
> ____ ____ __
> | | | |__| |
> | S1 | | S2 | |__|
> |____| |____|
>
> The systems behave identically.
> The systems use identical set of messages to communicate
> with a service and the sequences of exchanged messages are also identical.
>
> We would like to know about whether the intrusion into the S1
> is harder than the intrusion into S2 and how to describe these
> systems in a formal manner.
Suppose hypothetically that the smart card in S2 made it physically
impossible to retrieve the key. You could only request that the smart
card encrypt or sign specific values. In this case, someone who
compromised the software security of general purpose computer S1 could
construct a duplicate of it, whereas that would not be possible for S2.
Perhaps they could dupe S2 into signing/encrypting/decrypting on their
behalf, but they couldn't construct a duplicate of it.
DS
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: "The code book" where
Date: 17 Oct 2000 21:32:23 GMT
>[EMAIL PROTECTED] writes:
>I have just ordered "The code book" but I have to wait 3-4weeks before
>I can get it. Do somebody know where I can download an PFD of it,
>becouse I will like to spend some time whit breaking the codes?
>
>Best reg.
Although the codes have all been cracked, the discussion egroup
is still going at:
http://www.egroups.com/files/CipherChallenge/
You'll find an electronic version of the codes in the "Files" section.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: SALT + stream cipher
Date: Tue, 17 Oct 2000 21:46:22 GMT
In article <[EMAIL PROTECTED]>,
John Myre <[EMAIL PROTECTED]> wrote:
> Simon Johnson wrote:
> <snip>
> > A decrease in entropy can occur in an hashing algorithm? Is this
true,
> > can you present a logical argument for this?
> <snip>
>
> The output is some fixed size; the input could be larger; and
> the input could (conceivably) have full entropy. Q.E.D.
>
> This is presumably a theoretical rather than practical
> restriction, as passphrases practically never have more
> entropy than the hash size.
Every step of the hash is reversable so the lost of entropy is with the
redundant mixing of input words into a smaller size of registers.
If you think of a SHA-1 as a 160-bit block cipher you will see what I
mean. There is a loss of information but the goal of the hash is to
make it intractable to exploit.
Tom
>
> JM
>
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Eric Lehman <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: Re: A new paper claiming P=NP
Date: Tue, 17 Oct 2000 22:01:46 GMT
I gave this paper a serious shot.
It is a total mess. The quality is far below mainstream publication
norms. The guy can't write one coherent sentence. He uses non-standard
terms and acronyms for everying. Partly this is language, of course,
but I'm used to foreign-authored papers and this is different: there is
carelessness beyond the simple language issue. But Stas and others
helped me along at some points, and I made it a considerable distance.
(Thanks, guys! :) )
I presently found errors in the first algorithm, the first theorem, and
the first major example. These were repairable, but why should anyone
believe the guy's astonishing overall claim, when he can't seem to get
anything else right?
Reading further, I discover that Anatoly gives no evidence of any deep
knowledge of the mathematics he's working with. Everything you need to
know to understand this paper is taught in the first few weeks of a Math
for Computer Science course. No passing mention of perfect graphs or
the theta function. Not damning, but not reassuring either.
Next, I find that the author's first new algorithm lacks a proof of
correctness! This is simply astonishing. The guy spends a page on
"relations"-- the most trivial of matters-- and doesn't devote one
sentence to showing that his construction of a "vertex saturated
digraph" actually _works_!? Wooow...
Then I found this posting on the Theory Edge discussion group. (I
believe that the author is a moderator for the group.)
> hi everyone, just a little note for anyone evaluating
> the paper. stas told me with an earlier paper of
> anatoly's, part of the problem was that a procedure
> described in the paper failed to halt for some
> instances. it did in fact work fast for many
> instances, but for some it seemed not to terminate..
> specifically it "cycled" through configurations that
> went in a loop as I recall, and it
> took Stas a long time (around a month or more)
> to find an instance for which it didn't terminate.
>
> also, full disclosure: stas told me that
> anatoly did not acknowledge this initially after
> prodding him (sorry guys, my loyalty
> is with the community on this one in posting this information..
> I respect privacy of email in general but consider this
> fair disclosure).
This is precisely what a careful proof of correctness would prevent, of
course.
In summary, for what my opinion is worth: this is no more a proof that
P = NP than is your local phone book. K's and O's are swimming in the
air, threatening to form a descriptive word...
/Eric
------------------------------
** 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
******************************
