Cryptography-Digest Digest #480, Volume #13 Tue, 16 Jan 01 20:13:01 EST
Contents:
Re: Bias fix (was Re: How do I fix?) (Benjamin Goldberg)
Re: Any good source of cryptanalysis source code (C/C++)? (Tom St Denis)
Re: Any good source of cryptanalysis source code (C/C++)? (Wesley Horton)
Re: Comparison of ECDLP vs. DLP (DJohn37050)
Re: multiple anagramming? (Andru Luvisi)
Re: NSA and Linux Security (digiboy | marcus)
Re: A Small Challnge ("rosi")
Entirely encrypted operative system or file system (alberto65)
Re: A Small Challnge ("rosi")
RSA sign in 40ms on a DSP ? ("Charles Oram")
Re: Any good source of cryptanalysis source code (C/C++)? (AllanW)
----------------------------------------------------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Bias fix (was Re: How do I fix?)
Date: Tue, 16 Jan 2001 21:15:04 GMT
Benjamin Goldberg wrote:
[snip]
> What about with 8 bit words?
> word_out_dif = (1 - (1-word_in_dif)^2) * 255/65535
> After the first round, each word has a probability of changing of
> 0.98837221, and after the second, 0.996093743. Beyond this, all
> subsequent rounds it displays as 0.99609375, which is precisely
> 255/256 to the limits of the precision I have available. So, with 8
> bit words, 3 rounds are needed for SAC.
Whoops, that's actually only to 10 decimal places, the display
precision, not the precision of the "double" value.
Actually, I need 4 rounds for SAC with 8 bit words and a 3 layer FFT.
> With a 4 layer FFT, and 8 bit words, 2 rounds are sufficient for SAC.
Similarly, this should be 3 rounds.
Of course considering that double has about 64 bits of precision (and
not all of that is mantissa), I would go further to say that 4 rounds
are needed for safety. Four rounds also has the advantage of being a
power of two, which is good for key scheduling.
Wow. I'd originally posted the cipher with 4 rounds, with 4 having been
chosen arbitrarily, then suggested that it might be secure with 1 round,
then discovered it wasn't, then found, by *calculation* that what I
needed was precisely 4 rounds. Right back where I started (except that
I'm more knowledgeable now). Wierd.
--
Unofficial member of the Procrastinator's Club of America. I haven't
applied for my membership card yet, but I'll get around to it. Really I
will. Really!
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Any good source of cryptanalysis source code (C/C++)?
Date: Tue, 16 Jan 2001 22:00:39 GMT
In article <3a647b68$[EMAIL PROTECTED]>,
"Ryan Phillips" <[EMAIL PROTECTED]> wrote:
> Haider, check the faq. Now people, when I come to a newsgroup I expect a
> little courtesy and a little help - a link to the faq would have been nice.
> Tom if you don't want to help, don't post a message.
Don't tell me what I shall and shall not do.
Tom
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Wesley Horton <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Any good source of cryptanalysis source code (C/C++)?
Date: Tue, 16 Jan 2001 16:18:29 -0600
With regards to Tom's comment:
Maybe people should use their heads before posting? A lot of times if
the OP
just used a web search they would find their answers...
It's laziness to the max, man.
Not necessarily Tom, A quick check on google.com shows 39,100 listings
for cryptanalysis alone. While I agree that reading the FAQ is always a
good start, you have to agree that there is as much good information out
there as there is bad information. I don't know that asking which is a
better source of information is inappropriate. Now I will state
categorically, if the guy posted a note here and said, something like,
"I've just figured out a new unbreakable code, here, see if you can
break it!" should be ignored. But what if the same guy was offering a
$5000 prize if someone broke it? Bit of a different story . . .Anyway .
. .
Regards,
Wesley Horton
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Date: 16 Jan 2001 22:41:21 GMT
Subject: Re: Comparison of ECDLP vs. DLP
Here is a totally dumb way a candidate RSA public key MIGHT be invalid. The
modulus is prime, due to a bit flip. I call this a "toy" example, just to show
it is possible. Now ANYONE can invert the operation of this pseudo-RSA public
key.
There are many more ways a candidate RSA public key MIGHT be invalid, if the
modulus is easy to factor, it is easy to invert. Or if it is hard to factor,
it means that the (encryption) operation (for example) cannot be inverted by
anyone, including the owner.
The Netscape RNG flaw was NOT due to a HW or SW bug, it was due to a design
mistake, the SW/HW operated as intended, but the design was flawed to use such
a small PRNG seed.
So you have HW/SW that uses a big enough random seed and has code to do the
calc as specified in the standard. You might even have system validation that
shows you generated 1,00 or 1000 keys correctly. Now, you generate YOUR key,
how do you know it is any good?
I will grant that for many purposes it is fine to be able to just trust that
things went right this ONE time that is really counts. But this trust is
actually a cost/benefit decision. If I want more assurance, I do more tests.
If I have a $20 max loss key, I MIGHT do no tests. If I have a bet-the-company
key, I might do LOTS and LOTS of tests, if appropriate.
Don Johnson
------------------------------
From: Andru Luvisi <[EMAIL PROTECTED]>
Subject: Re: multiple anagramming?
Date: 16 Jan 2001 15:12:43 -0800
Mok-Kong Shen <[EMAIL PROTECTED]> writes:
[snip]
> I am sorry to express some opinions concerning your original
> post that would certainly displease you. If all books are
> freely available on the internet (or in whatever form), don't
> you think that the motivations of (at least plenty of) authors
> to write books and that of (all) publishers to publish them
> would disappear?
Absolutely not.
I have purchased books whose full text I have available online, just
as I have also purchased software which I can download for free. My
reasons are many, including having a print copy to read in the bath
tub, and supporting the efforts of the authors.
...and I am not the only one.
Andru
--
Andru Luvisi, Programmer/Analyst
Quote Of The Moment:
Churchill's Commentary on Man:
Man will occasionally stumble over the truth,
but most of the time he will pick himself up and continue on.
------------------------------
From: digiboy | marcus <[EMAIL PROTECTED]>
Subject: Re: NSA and Linux Security
Date: Tue, 16 Jan 2001 23:38:18 GMT
90%
--
[ marcus ] [ http://www.cybergoth.cjb.net ]
[ ---- http://www.ninjakitten.net/digiboy ]
Sent via Deja.com
http://www.deja.com/
------------------------------
From: "rosi" <[EMAIL PROTECTED]>
Crossposted-To: sci.math,comp.theory
Subject: Re: A Small Challnge
Date: Tue, 16 Jan 2001 19:34:03 -0500
First, thanks for the interest of you all.
>>>> The formal part says it _ALL_. <<<<
People who would rather have no details may skip this message.
Some may want to draw some 'parallel'. But I doubt. In the whole
history of cryptography, not geometry :), there might have been _NO_
parallel. To be exact, the notion of QP might have had no public
appearance before I proposed it (informally here in sci.crypt quite some
time back). There could have been contemplations of it, but as far as I
know, nobody else ever made it public, or quasi-public. :)
Since the formal part says it all, please stick with the formal part.
If one reads it carefully, seriously and sincerely I am sure one can get
it. It is not that hard and, blessed, it is not that long either. There
are only a few lines (about the E's and D's).
Let me be very specific this time. It is not guaranteed that every
public-key method can work this way. If anyone could make RSA work that
way, then he had in effect answered part of the challenge (the design
part). What was left was ONLY :) the complexity part. Terrific! IF (BIG
IF) it can not, then I wonder if (small if) we can just for a tiny
fraction of our lives get away from RSA for a slight change???
What Mike Scott proposed is something concrete, something that makes
sense. But remember what I said about semi-public and what I said about
QP. They are totally different. Semi-public is a mode in which one operates,
by keeping some security-independent secret. If the problem posed by this
mode of operation is 'harder', so be it. Security is only a threshold.
Something is either secure or not. It is a word carrying the superlative,
just like the word wrong or right. So in fact 'harder' in this sense is
just nonsense. QP is not an operation mode, it is a different concept (of
building security)!
In addition, what is normally known as randomization or random noise
(such as in McEliece or NTRU) is neither semi-public nor QP. In public
keying that supports semi-public keying, some _PUBLIC_ parameter is kept
secret when in semi-public mode. The randomized parameters are NOT public
parameters. However, in a semi-public able keying scheme, the 'secret'
can be changed at will WITHOUT the need for changing the entire public
key. Therefore, even if it can ever be tweaked to work in semi-public
mode, a public-key scheme is not by default a semi-public one either.
DES(RSA(m)) is neither semi-public nor QP. I do not know what to call it.
Unless it is "that" type of keying scheme already, tweaking may not do
the magic. I am not saying forget about it. If you can do it with RSA,
it could be interesting, not perhaps to a top notch cryptographer, but at
least to me.
So let us be concrete. Since so far, nothing in the posts has shown
even a remote relation to 'flavour one', I will only focus on 'flavour
two'. Anybody, I mean anybody, who wants to draw a 'parallel' can show
us in concrete terms:
Give us one (RSA or whatever) that works strictly abiding
by the definition. I can help here. It is simple. Just give
us two _DIFFERENT_ encryption keys and one corresponding
decryption key and the enciphered forms of some text by
each encryption key respectively. The decryptor takes both
versions of the enciphered text, having no idea which is
by which at this point, applies the decryption key and
obtains the original text which, by the way, can be random
bits.
Congratulations! You got IT!
--- (My Signature)
NOTE:
If you have already succeeded in the 'two enkey' case, try to see if you
can extend it to a _THEORETICALLY_ infinite enkey case.
Caution: Do not over-read the formal specification, which says about
different encryption keys producing different ciphertexts from a same plain-
text message, but does not specify how they should be different. There is
no restriction here. Just read what the formal spec says. No more and no
less.
------------------------------
From: alberto65 <[EMAIL PROTECTED]>
Subject: Entirely encrypted operative system or file system
Date: Wed, 17 Jan 2001 00:01:02 GMT
I mean, the computer boot, and then ask a passphrase.
Then it begin to load the kernel of the OS using decrypting it.
Or, more simply just decrypt the encrypted file system....
Do you know if someone has made something like that?
Thanks.
------------------------------
From: "rosi" <[EMAIL PROTECTED]>
Crossposted-To: sci.math,comp.theory
Subject: Re: A Small Challnge
Date: Tue, 16 Jan 2001 19:52:45 -0500
Mok-Kong Shen wrote in message <[EMAIL PROTECTED]>...
>
>
>rosi wrote:
>>
>[snip]
>> Having said this, I encourage you to read carefully the formal part.
>
>Sorry for posing some questions of ignorance, for I have
No. The questions are some of the most intelligent ones you can
ever see in sci.crypt.
>some essential difficulty to understand your scheme.
>
>(1) Suppose A is the receiver (he distributes all encryption
> keys, while keeping the decryption keys) and B and C are
> the intended senders and R is the rest of the world.
> Do B and C each obtain a single and distinct encryption
> key? How many decryption keys does A have (for receiving
> messages from whom)? Does R get anything?
I believe you already got it!
Since it does not matter which of the (possibly INFINITE)
encryption keys is used to encrypt, the decryption key has
no discrimination. In addition, poor A has only ONE dekey. :(
You let A, B, C, R or whatever you would like to have ONE
of the billions upon billions of encryption keys. Repeat, they
all can have it. Anyone who wants to have it, can. And anyone
who does not want to have it, can have it as well.
To save another round, I ask the next possible question
for you: Can A publish more than one such encryption keys?
That is the implicit part which I think you all can answer with
no difficulty. Forgive me for not making it explicit. (Making
it explicit matters little as far as a working secure scheme
is concerned).
>
>(2) Are you sure that some practically useful D and E[i] and
> E[j] with E[i]!=E[j] could satisfy your following requirement
> for arbitrary m in a sufficiently large set?
>
> D(E[i](m)) = D(E[j](m)) = m
>
Yes. Absolutely! That gives 'the' security I want but can not
find ANYWHERE else. I do not know about R (rest of the world)
and what that want and I should not care. :)
To put this little piece of your doubt to ease, I can tell you that
it is very practical. In fact, it is one of the fastest, if not THE
fastest, asymmetric encryption systems of today! Forgive me
for reading between the lines sometimes. You sounded like
asking 'possible?' instead of 'practical?'.
Finally, Mok-kong, it is amazing that you focused on the real
issues so fast. I think it is because you are honest, sincere,
serious and open-minded. Thank you very, very much.
>M. K. Shen
------------------------------
From: "Charles Oram" <[EMAIL PROTECTED]>
Subject: RSA sign in 40ms on a DSP ?
Date: Wed, 17 Jan 2001 13:30:50 +1300
Hi there,
I'm looking at an application where I need to do a 512bit RSA encryption
using the private key (i.e. sign) on an 80MHz Motorola DSP56301 in around
40ms. At this stage all I have to do is say whether or not it can be done -
does anyone have experience with optimised implementations of this sort of
thing on a DSP or embedded processor who could tell me whether they think it
can be done that quickly, or am I kidding myself ?
I've had two different 'C' code implementations running on the DSP and this
proves that I will definitely need to use an optimised set of large integer
routines, probably mostly written in assembly language. I am also planning
to make good use of the DSP's 24 bit multiply and add instructions (can do a
24x24bit multiply into a 56bit accumulator).
I have looked at the web page for CASCADE
(www.dice.ucl.ac.be/crypto/cascade) where they claim to have an
implementation on an 17 MIPS ARM7 that can do an RSA sign in 73ms. Making
the (not necessarily true) assumption that it can be as efficiently
implemented on the 80 MIPS DSP would indicate that it may be possible to do
it in 16ms.
Thanks.
Charles Oram.
------------------------------
From: AllanW <[EMAIL PROTECTED]>
Subject: Re: Any good source of cryptanalysis source code (C/C++)?
Date: Wed, 17 Jan 2001 00:46:46 GMT
"Haider Ali" <[EMAIL PROTECTED]> wrote:
> I am looking for any good cryptanalytic attacks on block
> ciphers, programmed in C/C++ (I need the source code).....
Boy, what timing! -- are you in luck!
It just so happens that I've discovered an absolute sure-fire can't-miss
way to decrypt absolutely ANY encryption scheme. I've tried it, and
believe
me: it WORKS! But now the CIA and the NSA and other organizations are
on to
me -- they want to take my algorithm away from me, to make sure that it
doesn't fall into the hands of any foreign governments, not even
friendly
ones.
But I can't let this important algorithm die this way. I have to tell
the
algorithm to all interested parties in the whole world, and I have to
do it
quickly, before the government forces me to make it secret again. So
right
now, for the very first time ever (and possibly for the last time
ever!),
I'm willing to share the secrets of this algorithm with everyone on this
newsgroup for absolutely free. Why? Because I'm just crazy enough to do
it.
I got the idea for this decryption from the people that claim to be
able to
create a one-time-pad from pseudo-random-number generators, thereby
getting
all of the OTP's benefits without any of it's weaknesses. As you
probably
know, when an OTP is properly applied, the decryption process is
completely
impossible because any cleartext of equal length to the cryptotext is
equally likely to be correct. Thus the cryptotext "Fi@[A" could stand
for
"SMOKE" or "Kiss?" or millions of other possible cleartexts -- there's
no
good way to tell, except perhaps for common sense.
But that particular concept only works for OTP, because (unless there
are
garbage bits added to the end of the message) the ciphertext is always
exactly the same length as the plaintext. Other encryption or code
schemes
could easily change the length; it could use encryption, or it could add
noise or other data, or even a combination of these things, making the
original cleartext length difficult to guess.
But not impossible, right? I mean, surely if the ciphertext is 2Kb, then
the cleartext couldn't have been longer than about 4Kb or so, right?
And it
couldn't have been too much shorter than 2kb -- heck, we know that the
cleartext was at least 1 byte, and this isn't THAT much shorter than
2kb.
Using this concept, and the equally-likely concept, it's a simple
matter to
take an estimate of the original cleartext message length, and then
generate all possible permutations of data that length. Note that
non-printable data, such as executable programs or already-encrypted
data
files, are among the possible cleartext files that we must generate in
order to be thorough.
Naturally, anything that seems too good to be true probably is. In this
case, there are two problems that restrict the usability of the program:
1. The high number of possible cleartexts for any given cleartext
length
is enormous -- as the estimated length of the cleartext grows
linearly, the growth of the number of possible cleartexts is
literally
exponential. So to use this program you're going to need a very
fast
computer with a fast hard drive, and plenty of patience.
2. It may be difficult to tell when the program has finished. The
program
can tell you that a given cleartext could POSSIBLY have been the
input
to the cipher, but it's up to you to say if this really is the
right
data or not. ...But come on, how hard could this be, right? You
must
want to decrypt the data for some good reason. Whatever the reason
is,
you're certainly going to know if the cleartext satisfies that or
not!
If so, stop decrypting -- you're done. If not, then just keep going
until you find the cleartext that does work.
On the other hand, this decryption algorithm has two benefits that I
don't
believe are featured in any other decryption algorithm I've ever heard
of.
1. It works with ANY type of encryption system, including ones that
haven't even been written yet.
2. It is possible to decrypt the ciphertext without bothering to
intercept it first. So long as you have at least a vague guess
about
the length of the original cleartext, you do not need the
ciphertext
at all!
Here, then, are the TWO programs you can use to break ANY encryption
codes.
Note that they have NOT been tested, but since you wanted C/C++ source
code,
you should be able to fix any minor problems you run into.
// DecryptFirst.Cpp
//
// This first program in the "Decrypt-Any" suite is used to generate the
// very first version of the cleartext for any given length N. The first
// command-line argument is the name that you want to use for the
cleartext
// file, and the second argument is the assumed length of that file. (If
// the length proves to be wrong, you will have to start over with the
// next-larger or next-smaller size.)
//
// For instance, if you want to store the text in ClearText.Txt and you
// believe that the original cleartext data was only 5 bytes long, you
would
// type:
// DecryptFirst ClearText.Txt 5
//
// The program always exits with status code 0.
//
// Note: Error handling has been ignored for simplicity.
//
#include <cstdio>
using namespace std;
int main(int argc, char*argv[]) {
FILE *f = fopen(argv[1],"wb");
for (int i=atoi(argv[2]); i; --i) fputc(0,f);
fclose(f);
return 0;
}
// DecryptNext.Cpp
//
// This last program in the "Decrypt-Any" suite is used to generate the
// N+1th possible version of the cleartext. The first command-line
argument
// is the name that you use for the cleartext file. The second argument
is
// the assumed length of that file; theoretically we could manage
without
// this, but it helps to simplify and speed up the program, because we
// don't need to search for the end of the file. If this argument does
not
// match the name of the file given in the first argument, the results
are
// undefined.
//
// For instance, if you are continuing to store text in ClearText.Txt
and
// you believe that the original cleartext data was only 5 bytes long,
you
// would type:
// DecryptNext ClearText.Txt 5
//
// You can also modify routine PreCheck(). The purpose of this routine
// varies:
// * As the name indicates, you can use it to perform a simple pretest
// to see if the new file contents could possibly be the cleartext
file
// you're hunting for. For instance, if you know that the E-mail
// message is pure ASCII, you could reject any input files that
include
// non-ASCII bytes.
// * Another possible use of this routine is to do THE cleartext
hunting.
// If you're able to look for some particular charactaristic of the
// cleartext, such as a signature and valid CRC, then you can embed
// that check directly into the DecryptNext program to improve
// execution speed.
// * By default, PreCheck() does nothing significant; it considers all
// input to be a possible "match," so that the user can perform any
// additional checking.
// In any case, this routine must return one of these values:
// true -- if the file MIGHT be a valid cleartext file and the user
// should check to see.
// false -- if the file could NOT be a valid cleartext file. The
// program will skip this possibility and go on to the next
one,
// without ever asking the user to check the file manually.
//
// The program exits with a status code, signifying it's current state:
// 0 -- We have found another possible cleartext file. (You must
// use some person or some other program to check the results; if
// the "real" cleartext has been found, quit executing
DecryptNext.
// Otherwise, continue.)
// 1 -- We have exhausted all possible combinations where the
cleartext
// is this length. You should re-run DecryptFirst with a new
// different length, and continue.
//
// Note: Error handling has been ignored for simplicity.
//
#include <cstdio>
using namespace std;
bool PreCheck(const char*data); // Prototype
int main(int argc, char*argv[]) {
// Get length of file
const int filelen = atoi(argv[2]);
// Read existing version of file
char *buffer = new char[filelen];
FILE *f = fopen(argv[1],"rb");
fread(buffer, 1, filelen, f);
fclose(f);
do {
// Find the last character that isn't \xFF
int i;
for (i=filelen-1; i>0; --i)
if (char(-1)!=buffer[i])
break;
// The whole buffer is nothing but \xFF
if (char(-1)==buffer[i])
return 1; // Exhaustive search failed
// Increment that character, then set everything after it to 0's
for (buffer[i]++; i<filelen; ++buffer[++i])
return 1;
// If this data passes muster, quit altering the file
} while (!PreCheck(buffer));
// Precheck gives it a go (or there's no precheck)
f = fopen(argv[1],"wb");
fwrite(buffer, 1, filelen, f);
fclose(f);
return 0; // We have a possible match!
}
// This default version of PreCheck just ITCHES to be customized as
// explained all abover. Do NOT change any of the characts pointed to.
bool PreCheck(const char*) { return true; }
How to use the free program suite:
1. Compile both programs.
2. I'm thinking of a 5-letter word, meaning "juicy and sinful." Since
you
don't need any sort of encrypted text, you're now ready to crack it.
3. Initialize the run by executing this command:
DecryptFirst word.txt 5
4. Examine the file word.txt. Is this usable and readable? If this is
the
obvious plaintext message, we're done. Otherwise, continue these
steps.
5. Try the next word by executing this command:
DecryptNext word.txt 5
6. If step 5 returned code 0, then repeat steps 4-6. Eventually you will
find the plaintext, or else step 5 will return code 1.
7. Step 5 returned code 1, so the plaintext is NOT 5 letters. Repeat
steps 3-7 with a different word lengths; perhaps a 4-letter memo is
just as likely. (This won't happen in the current example.)
8. After about 250 billion iterations, the word.txt file holds the word
"Apple." This fits the clue, so you stop the search.
Congratulations, you win!
--
[EMAIL PROTECTED] is a "Spam Magnet," never read.
Please reply in newsgroups only, sorry.
Sent via Deja.com
http://www.deja.com/
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
