Cryptography-Digest Digest #755, Volume #11 Thu, 11 May 00 15:13:01 EDT
Contents:
Re: Key generation for lja1 (Tom St Denis)
Severe security flaw in FineCrypt v2.1 (repost) (=?iso-8859-1?Q?Emmanu=EBl?=
Sustronck)
Re: UK issue; How to determine if a file contains encrypted data? (Jeffrey William)
Re: Newbie question about generating primes (Thomas Scharle)
Re: RSA-primes, smoothness (Jerry Coffin)
Re: high speed public key crypto (Jerry Coffin)
Re: More on Pi and randomness (Jerry Coffin)
Re: An argument for multiple AES winners (David A. Wagner)
Re: Request for cryptanalysis: lja1 (Andru Luvisi)
Re: An argument for multiple AES winners (Roger Schlafly)
Re: Newbie question about generating primes ("Dann Corbit")
----------------------------------------------------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Key generation for lja1
Date: Thu, 11 May 2000 17:30:54 GMT
=====BEGIN PGP SIGNED MESSAGE=====
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Mark Wooding) wrote:
> Only if you do it badly.
>
> Given a function R() which returns a uniformly distributed random
> integer 0 <= x < N, I can choose a uniformly distributed random
integer
> 0 <= x' < n for any n <= N[1], with an expected number of discarded
> results from R() less than 1 per output.
>
> Choose c as the largest integer such that c n <= N. Let x = R().
> If x >= c n, choose another x. Otherwise let x' = floor(x / c).
>
> Now note that c n > N / 2 -- otherwise the hypothesis that c is the
> largest integer with c n <= N is violated. Hence the probability
> of a discard is less than 1/2, so the expected number of queries to
> R() per output is less than 2, so the expected number of discards
> is less than one.
That's just it, on binary computers you can't uniformly pick random
numbers mod anything that isn't a power of two. Unless you seed a
prng with the private key and do something like
rand(N)
{
while ((a = prng()) >= N);
return a;
}
> > I would just do something like this:
> >
> > for i = 0 to 767 do
> > x = rand() mod 256
> > y = rand() mod 256
> > swap(x, y);
> > next i
>
> Intuitively I distrust this construction. My suspicion is that it
only
> provides a uniform shuffle as the number of iterations (here, 768)
tends
> to infinity. I don't have time to work out a proof or
> justification
for
> this claim right now.
This is true but after 768 swaps the array is fairly random. Again
you need a prng for this too....
Oh well... in my sboxgen.c I just do 3n random swaps to get the next
'random' permutation.
Tom
=====BEGIN PGP SIGNATURE=====
Version: PGPfreeware 6.5.3 for non-commercial use <http://www.pgp.com>
Comment: http://www.tomstdenis.com/
iQCVAwUBORrva3Daq5QeLg0RAQG+ogP/QXZLbN+NQBLyDVKgK5CF56wn+4gfkR/Q
2EB8Ncl1t+EVySHU0pl3Gf9b2hr/ESxCBJClIzC4coj6qQDc+u2+aILjwhzG2KdV
Z8PrnbjfRXJW9J/di8657ZQjC/9F2tsbgONbhiEvMWYfV0DXma//LP7L9jBqcGlO
6JWxMv5yrKw=
=jpL6
=====END PGP SIGNATURE=====
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: =?iso-8859-1?Q?Emmanu=EBl?= Sustronck <[EMAIL PROTECTED]>
Crossposted-To: comp.software.testing
Subject: Severe security flaw in FineCrypt v2.1 (repost)
Date: Thu, 11 May 2000 17:42:48 GMT
(Repost due to apparent NNTP-server lockup)
FYI: FineCrypt v2.1, discussed here a while ago, has a severe security
flaw in one of its components. The author, Sergey Kuznetsov, stopped
replying to my mail regarding this flaw and some other weird issues with
his program and website. Correspondence is included below.
--
Best regards,
Emmanuël Sustronck
======== Original Message ========
Subject: Re: Huge bug in FineCrypt v2.1
Date: Fri, 21 Apr 2000 04:49:23 +0200
From: Emmanuël Sustronck <[EMAIL PROTECTED]>
To: [EMAIL PROTECTED]
References: <[EMAIL PROTECTED]>
Dear Mr. Kuznetsov,
Thank you for your reply. Unfortunately, the security flaw persists.
I installed FineCrypt again, in directory "C:\Program Files\FineCrypt"
instead of the default "C:\Program Files\Crypto Systems\FineCrypt v2.1"
and used the registration info you provided to unlock the full version.
I created a self-extracting encrypted archive, containing some PDF
files. The password used for encryption was "thisisatest". When the file
was executed, it accepted *any* random password of 8 characters or more
and decrypted the files correctly. The same test file was executed on
different computers, which didn't have FineCrypt installed, and all
yielded the same results. I have included this file as an attachment:
please try it out. It will accept "thisisatest", "azertyuiop",
"qsdfghjklm", and any other password of minimum 8 characters in length,
and decrypt the files correctly.
However, the FineCrypt help file clearly states: "After you have entered
the password, FineCrypt with the help of special secure method (see
Technical Notes), generates a key of maximum length for the current
algorithm from the passphrase. This key will then be used for
decryption." This is simply untrue. Moreover, the "Technical Notes" this
excerpt refers to were not found in the help file.
These results cannot be explained otherwise than what I concluded in my
previous e-mail: the CAST-128 decryption key is stored with the
encrypted file, and the executable is only designed to perform a simple
yes/no check on the password before using the decryption key.
One could argue that this phenomenon apparently only manifests itself
when self-extracting encrypted archives are made with FineCrypt
installed in another directory than the default one. However, I find it
difficult to believe that an encrypted executable made with an
installation in the default location would use a completely different
algorithm. I wouldn't be surprised to see that anyone with some
disassembly skills can easily crack such files. Besides, it wouldn't be
a real "solution", since I am probably not the only one on the planet
who sometimes installs applications in other directories than the
default one.
One could argue that the normal, non-self-extracting, encrypted files
appear to be secure, but that also is a very poor workaround. The single
reason why I evaluated FineCrypt was precisely the ability to create
self-extracting encrypted archives. The FineCrypt website even presents
this feature as one of the most important: "... more and more people
prefer to use strong encrypted self-extracting archives created with
FineCrypt." Besides, any encryption program with even the most minuscule
flaw in any of its components is an unsecure encryption program, and
hence useless.
This discovery might have even more severe implications. The mere fact
that you are the programmer would imply that you must be aware of the
fact that your program doesn't actually do what you claim it does, which
would make all this far more than just a simple bug. Why would someone
do this? Looking for a quick buck? Hired by the KGB to spread insecure
encryption? This is extremely worrying.
If the customer figures on your website are correct, then you have
(willingly?) put the privacy of over a million people at risk and even
made them pay for it. Then you would have made over 24 million dollars
(1,200,000 times $19.95) with an inherently insecure product. I would
start seeking legal counsel if I were you...
But there are more weird things about FineCrypt. A search for the
"National Institute of Cryptographic Research" on Metacrawler yielded no
other complete match than your FineCrypt website. What is this
mysterious institute your website refers to and even received a "Seal
for trusted software" from?
Does this "National Institute of Cryptographic Research" really exist?
>From what country is it a "National Institute"? Phantasialand? Have you
really received a "Seal for trusted software" from them, assuming that
they are a respectable organization? Are you really "The world leader in
encryption software"? <grin> Do you really have 1,200,000 registered
users? Who are these "independent reviewers" that "agree that FineCrypt
2.1 is the most reliable, manageable, and secure way for data
encryption"? Why is PGP not already swept off the market? Does the
expression "Rock-solid platform for data encryption" have a different
meaning in Russia than in the rest of the world?
In your e-mail, you say that you "guarantee reliable encryption with all
algorithms, but *only* in encryption with password and in encryption
with user key". What other methods of encryption would there be besides
these two, and why would they be unreliable? In what documentation would
that be outlined?
Also, you refer to the testing of files encrypted with a user-specified
key. I thought I made it quite clear that the anomaly I discovered
applied to files encrypted with a password-generated key. That answer
was completely off-topic.
I am sorry, but I can no longer trust your program, whatever the next
version is going to be. Unless you can provide a satisfactory
explanation and resolution for these weird results, I will be forced to
alert my colleagues about this serious security flaw; and I suggest you
do the same. It would only be good business practice if you immediately
alert your alleged 1,200,000 customers and place a huge banner on your
site warning and apologizing for this bug.
I hope to hear from you soon.
--
Best regards,
Emmanuël Sustronck
[EMAIL PROTECTED] wrote:
>
> Dear Mr. Sustronck,
>
> thank you for your very useful letter. Yes, english on our site is rather
> poor, and we are working on this issue. As for the "bug" in
self-extracting
> archives, this is not exactly the bug. We guarantee reliable encryption
with
> all algorithms, but *only* in encryption with password and in encryption
> with user key, but in next version this "bug" will be fixed. You can even
> check reliability of encryption with user key (read online help topic
"Test
> FineCrypt with user key"). You can check with the test vectors only the
> registered version of FineCrypt (because of key length).
>
> Your user name: Emmanuel Sustronck
<registration key clipped>
>
> Please, make the following in order to register FineCrypt:
>
> 1. In the main FineCrypt window from the "Help" menu select "About
> FineCrypt...". In the appeared dialog box press the "Register" button.
>
> 2. In the "Register" dialog box enter your user name and registration key
> exactly as they appears in this message.
>
> 3. Press "OK" button.
>
> Best regards,
> Sergey Kuznetsov,
> "Crypto Systems, Inc."
>
> -----Original Message-----
> From: Emmanuël Sustronck <[EMAIL PROTECTED]>
> To: [EMAIL PROTECTED] <[EMAIL PROTECTED]>
> Subject: Huge bug in FineCrypt v2.1
>
> >
> >Dear Mr. Kuznetsov,
> >
> >I am currently evaluating your product for use on my system. At first,
> >everything looked fine, and I was about to buy a registration code...
> >until I detected an enormous bug in your program.
> >
> >When I created some self-extracting encrypted archives, I ran a test
> >afterwards to see how the program performs in decryption and
> >self-extraction. To my surprise, all self-extracting archives accepted
> >*EVERY* random password of more than a few characters in length, and
> >decrypted the files perfectly! In other words: the decryption key was
> >simply stored with the encrypted file!
> >
> >Then, I uninstalled the program and reinstalled it, this time in the
> >default directory instead of one I chose myself. The self-extracting
> >archives created from then on apparently worked as expected.
> >
> >This doesn't mean the problem is solved. It is clear that the encryption
> >key is not generated from the passphrase, but is a randomly generated
> >key, stored with the encrypted file. The self-extracting executable
> >apparently performs a simple check to see if the password matches, but
> >doesn't use it to generate the key.
> >
> >I urge you to take a close look at this bug, since it compromises
> >everything your program supposedly stands for. Some very interesting
> >articles on "snake-oil" on http://www.counterpane.com might probably be
> >of some help. Did *none* of your supposed 1,200,000 registered users
> >stumble upon this flaw?
> >
> >Oh, and by the way: using some decent English on your site wouldn't
> >hurt. For the supposed world "lider" in encryption software, who claims
> >"It's more and more people" prefer his software, especially with the
> >"grafic" statistics, it might be useful to provide a better "garantie"
> >for their data safety than what you're offering now.
> >
> >--
> >
> >Best regards,
> >
> >Emmanu?l Sustronck
> >
<Executable test file clipped>
------------------------------
From: Jeffrey William <[EMAIL PROTECTED]>
Subject: Re: UK issue; How to determine if a file contains encrypted data?
Date: Thu, 11 May 2000 12:54:14 -0500
zapzing wrote:
>
> Here in America, they are thinking
> of outlawing the science of Astronomy,
> because some astronomers have taken to
> tracking low earth orbit objects,
> including fedgov spy sattelites. They
> don't like that, so they just talk
> about outlawing astronomy. So when
> you find a favorable country, let me
> know.
Being an astronomy buff living in the USA, I was taken aback by this
statement. Could you please provide some references about this? And how
could you possibly
outlaw astronomy? Blind the entire populace?
------------------------------
From: [EMAIL PROTECTED] (Thomas Scharle)
Crossposted-To: alt.math
Subject: Re: Newbie question about generating primes
Date: 11 May 2000 18:13:32 GMT
I have another newbie question about generating primes
for cryptographic purposes.
I presume that the method that you choose to generate
primes will generate only a certain subset of the primes.
Wouldn't that reduce the search that someone would
have to do to find the prime factors?
--
Tom Scharle [EMAIL PROTECTED] "standard disclaimer"
------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Subject: Re: RSA-primes, smoothness
Date: Thu, 11 May 2000 12:29:07 -0600
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
[ ... ]
> I say it is snake oil because it gives an illusion of security
> when there actually is none. If someone wants to make an RSA key
> that he will disavow later, there are other ways:
IOW, taking steps that improve security are snake oil unless they
provide an absolute assurance of security.
By this standard, _all_ use of public-key encryption is snake oil.
The simple fact is, this step eliminates one entire class of weak
keys. It's quite effective in doing so. Yes, there are other ways a
key could be weakened, and there's probably no way to eliminate all
of them. This does NOT make it snake oil to eliminate one class of
weak keys, and saying it is simply makes you look foolish.
Don't get me wrong: I'm not saying that I think this particular
requirement is necessary, or necessarily even does a lot of good.
Harmless (if useless) appendages to otherwise strong encryption do
NOT turn it into snake oil.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Subject: Re: high speed public key crypto
Date: Thu, 11 May 2000 12:29:15 -0600
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
says...
[ ... ]
> I am ignorant of patenting in US, but I suppose you could with a not
> too big payment submit a patent application which secures your rights
> and which you can retract in case you later find that patenting isn't that
> advantageous for you. Then you can in the meantime let your stuffs be
> openly discussed in this group.
In the US, you can apply for the patent up to a year after open
publication of the method. As far as the possibility of an
inexpensive patent application goes, you're right: the US PTO allows
you to make a provisional application for a patent, without having to
try to write up the precise language of the claims, research of the
prior art and so on. You have a year from that point to submit a
non-provisional application. The provisional application DOES still
reqire a description of the invention, and has to be submitted by a
licensed patent agent or patent attorney. If the OP wants to
consider this route, he may wish to look at:
www.uspto.gov/go/attorney/
for a list of licensed patent agents and attorneys.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: More on Pi and randomness
Date: Thu, 11 May 2000 12:29:09 -0600
In article <8f9omh$qp3$[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
[ ... ]
> Using *named* transcendental constants is not cryptographically
> useful. There are not enough of them and whichever you select is easily
> guessed.
OTOH, perhaps it'd be interesting to start with something on the same
order as an RSA key uses: a pair of large, randomly chosen prime
numbers. Since the square root of an integer is always either an
integer or irrational (and since it's a prime, we know the square
root isn't an integer), take the square root of one, and use the
other as the position in the square root from which to start.
Finding the square root of a 100 digit prime to a length that is
itself a hundred digits or so is left as an exercise for the reader.
<G>
Of course, if you want to make it a bit more practical, there's no
particular reason for the second number to be either prime or
terribly large...
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: An argument for multiple AES winners
Date: 11 May 2000 11:05:13 -0700
In article <[EMAIL PROTECTED]>,
Sam Simpson <[EMAIL PROTECTED]> wrote:
> Details of he patent have been VERY well known about for some time.
> I don't think anyone who has any vague interest in cryptography were
> unaware that Hitachi has already asserted the same two patents
> covered SHA-1 (way back in August of 1998!).
Really? Probably I'm just showing my ignorance, but I'd never heard
of the Hitachi patent until just this year. Of course, one should not
draw any conclusions from a sample size of one :-), but are you sure
this patent was as well-known as you say?
------------------------------
From: Andru Luvisi <[EMAIL PROTECTED]>
Subject: Re: Request for cryptanalysis: lja1
Date: 11 May 2000 11:43:52 -0700
[EMAIL PROTECTED] (David A. Wagner) writes:
[snip]
> Note that there is no round-dependence, i.e., all rounds compute exactly
> the same deterministic function. Thus, there are slide attacks.
Where can I learn more about slide attacks?
> But, there are also more subtle attacks. Consider encrypting a plaintext
> of the form (X,X,X,..,X), i.e., one where all bytes take on the same
> value. If applying the compression scheme to the input (X,X,..,X)
> yields the output 0 (happens with prob. 1/256), then (X,X,X,..,X) is
> a fixpoint of the round function, and thus is left unmodified during
> all rounds of encryption. In other words, (X,X,X,..,X) encrypts to
> (X,X,X,..,X) with probability 1/256.
>
> These ideas can probably be extended to get a key-recovery attack.
I am having trouble figuring out how. You would know that key[key[X]]
= 0, but I'm not sure what that would buy you. I do still find this
property a little unsettling though. Since any permutation will be
both injective and bijective, there must be exactly one X that has
this property, and this will be key_-1[key_-1[0]].
[snip]
> By the way, once you make these tweaks, the question still remains how
> many cycles are needed. I don't know the answer, but at least I can
> say that you need more than just one cycle. There are easy attacks on
> one cycle of this scheme, since you can note that given known plaintext
> you can easily recover all of the F-function outputs; moreover, the
> F-function inputs are all known for the first and last rounds of the
> cycle, so this should be enough to recover the key[] array (certainly
> in a chosen-plaintext attack, perhaps also in a known-plaintext attack).
Indeed. I can see a chosen plaintext attack against one cycle with
keys having cycle length 256 which requires 2^16 chosen plaintexts,
and a maximum of 2^23 trial encryptions.
Of course, I would never *use* one cycle, just on general principle.
I've seen very few block ciphers with less than 8 cycles, and they
were designed by people far more knowledgable than myself. At least
two cycles would be needed in order to prevent an attacker from
knowing the output of any given round. They would still know the
inputs to the first and last round, though.
Andru
--
==========================================================================
| Andru Luvisi | http://libweb.sonoma.edu/ |
| Programmer/Analyst | Library Resources Online |
| Ruben Salazar Library |-----------------------------------------|
| Sonoma State University | http://www.belleprovence.com/ |
| [EMAIL PROTECTED] | Textile imports from Provence, France |
==========================================================================
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: An argument for multiple AES winners
Date: Thu, 11 May 2000 11:56:03 -0700
"David A. Wagner" wrote:
> Really? Probably I'm just showing my ignorance, but I'd never heard
> of the Hitachi patent until just this year. Of course, one should not
> draw any conclusions from a sample size of one :-), but are you sure
> this patent was as well-known as you say?
I don't think there is much reason to have heard of it. I have
never heard of anyone licensing it, or even expressing the opinion
that it is a significant patent. Has anyone here? Is there some
reason that we should care about this patent?
------------------------------
From: "Dann Corbit" <[EMAIL PROTECTED]>
Crossposted-To: alt.math
Subject: Re: Newbie question about generating primes
Date: Thu, 11 May 2000 12:05:18 -0700
"Thomas Scharle" <[EMAIL PROTECTED]> wrote in message
news:8fet8c$[EMAIL PROTECTED]...
> I have another newbie question about generating primes
> for cryptographic purposes.
>
> I presume that the method that you choose to generate
> primes will generate only a certain subset of the primes.
Since we can only generate finitely many, and there are an infinite number
of primes, your statement is trivially true.
> Wouldn't that reduce the search that someone would
> have to do to find the prime factors?
Let's suppose that we decide to create primes of exactly 256 bits. That
means that we know before-hand the first bit of the prime candidates!
Sounds limiting doesn't it? And primes at a size of 256 bits are much more
rare than primes at a size of 10 bits, for instance. Sounds even more
limiting!
But consider the prime counting function pi(x). It can be approximated very
well by the logarithmic integral or by Riemann's prime count estimator.
If you look at this web page:
http://mathworld.wolfram.com/PrimeCountingFunction.html
You will see that (for instance) there are 234,057,667,276,344,607 primes
with 19 digits or less (which also counts all with 18, 17, etc.). And there
are 2,220,819,602,560,918,840 primes with 20 digits or less. That means
that single digit gives us nearly ten times as many primes as all the primes
up to one digit less before it. By the time you get to hundreds of bits,
the addition of one more bit of length will add a prodigious number of
primes.
A simple way to generate primes of a given size is to pick some random odd
number with the number of bits that you desire. Then throw prime tests at
it. If it is not prime, add two to our large odd number and try again.
There are probably a lot more sophisticated ways than that also. At any
rate, large primes are currently very useful for secure communications
because of the RSA algorithm.
--
C-FAQ: http://www.eskimo.com/~scs/C-faq/top.html
"The C-FAQ Book" ISBN 0-201-84519-9
C.A.P. Newsgroup http://www.dejanews.com/~c_a_p
C.A.P. FAQ: ftp://38.168.214.175/pub/Chess%20Analysis%20Project%20FAQ.htm
------------------------------
** 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
******************************
