Cryptography-Digest Digest #754, Volume #13 Mon, 26 Feb 01 22:13:00 EST
Contents:
Hash strength question (Benjamin Goldberg)
RE: Rijndael S-box inverse ("Manuel Pancorbo")
Re: Improved stream cipher? (was: Re: Simple, possibly flawed, stream cipher)
(Benjamin Goldberg)
Re: Viewable Picture Encryption (Ben Cantrick)
Re: How to find a huge prime(1024 bit?) (Thomas Boschloo)
Re: Arcfour in Ada (Thomas Boschloo)
Re: Improved stream cipher? (was: Re: Simple, possibly flawed, stream cipher)
(Benjamin Goldberg)
Re: ECC implementation (Benjamin Goldberg)
Re: Super strong crypto (William Hugh Murray)
Re: "RSA vs. One-time-pad" or "the perfect enryption" (William Hugh Murray)
Re: Arcfour in Ada (Larry Kilgallen)
Re: Am I doing something silly by including my gnupghome with my (Benjamin Goldberg)
Re: Am I doing something silly by including my gnupghome with my (Benjamin Goldberg)
Re: The Key Vanishes: Scientist Outlines Unbreakable Code, Read it and Weep Boys
([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Hash strength question
Date: Tue, 27 Feb 2001 00:18:35 GMT
This might or might not sound like a silly question, but:
Suppose we have a hardware chip that can create a secure hash, which can
process data at X bytes per second.
Suppose we have a stream of data coming in at 2X bytes per second.
Does it weaken the security to take two hashing chips, send alternate
bytes of the stream to each chip, and when done, hash the two hashes
together?
eg:
stream = "abcdefghijkl"
hash = H( H("acegik") || H("bdfhjl") )
Is this hash more or less secure than doing H("abcdefghijkl")?
And if it is, does this extend to more than two hashes?
Also, can we use the H("acegik") XOR H("bdfhjl")?
--
A solution in hand is worth two in the book.
------------------------------
From: "Manuel Pancorbo" <[EMAIL PROTECTED]>
Subject: RE: Rijndael S-box inverse
Date: Tue, 27 Feb 2001 00:49:36 +0100
"Panu H�m�l�inen" <[EMAIL PROTECTED]>
> In Rijndael specification and some other papers it has been stated that
Rijdael
> encryption and decryption can share the S-boxes. Assuming that I have the
> encryption S-box, how can I use this to produce the inverse S-box?
>
for(j = 0; j < 256; ++j)
Sinv[S[j]] = j
BTW, are you parent of Riitta H�m�l�inen?
--
____________________________________________________________________
Manuel Pancorbo
[EMAIL PROTECTED] (Apply ROT13)
____________________________________________________________________
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Improved stream cipher? (was: Re: Simple, possibly flawed, stream cipher)
Date: Tue, 27 Feb 2001 00:52:44 GMT
David Wagner wrote:
>
> Henrick Hellstr�m wrote:
> >Here is a similar cipher that shouldn't be vulnerable to Scott
> >Fuhler'sattack. These are the changes:
> >
> >* Instead of initializing x to 1, x is initialized to state[7].
> >* Instead of adding either 0 or 1 to state[i] depending on a single
> >bit of x, x is added to state[i].
> >* In order to prevent attacks that exploit differential relations on
> >state[i], the state array is shifted up one byte and state[0] is set
> >to the value of the cipher text.
>
> I'm still left wondering about a comment I made earlier.
> It appears that such a cipher requires at least 8 table
> lookups per byte of output (as well as a few other very
> simple operations).
As someone else said, I was assuming you can optimize for hardware.
There, you can pipeline each state variable independently (as there is
no feedback backwards), and so pipelined each byte output would take one
sbox lookup, one xor and one conditional increment (or add). And,
software can do just as well, assuming you have a CPU with a bunch of
execution units... With 8 execution units, it takes only 3 or 4 cycles
per byte.
> How does this cipher compare in speed to, say, RC4 or
> SEAL? Does anyone have any performance measurements?
Dunno about SEAL, but I think RC4 takes 5 clock per byte.
Also, RC4 can't be optimized to be faster than that, due to the changing
sbox. Mine [in hardware] can be pipelined to be one clock per byte.
> If this is slower than RC4 and SEAL, is it worth spending
> a lot of time on?
I wrote it kinda as a toy. I expected it to be broken fairly quickly,
where "broken" means less than 2^64 work. However, for learning how to
break stream ciphers, attacking it is decent practice.
> Also, my earlier comments about the insecurity of using
> a 64-bit state still apply.
It was written as a toy. You could easily expand it to have a 128 bit
state.
> With X bytes of known text,
> one can break the cipher with 2^64/X work, and for X = 1MB,
> this is a disconcertingly low security level. There are
> also precomputation-based speedups (e.g., Hellman's
> time-space tradeoff) that should not be ignored.
Umm. Something seems a bit off about that relation. For 1 byte of
known text, you (supposedly) can break the cipher in 2^64 work. For
2^64 bytes of known text, you (supposedly) can break the cipher in 1
unit of work.
I don't think you can determine the entire state with one byte of
output, with 100% probability.
To process the 2^64 bytes of text is itself 2^64 work.
Am I missing something here?
--
A solution in hand is worth two in the book.
------------------------------
From: [EMAIL PROTECTED] (Ben Cantrick)
Subject: Re: Viewable Picture Encryption
Date: 26 Feb 2001 17:54:07 -0700
In article <_aCm6.478048$[EMAIL PROTECTED]>,
Chase <[EMAIL PROTECTED]> wrote:
>I have come up with an interesting concept that I would like to attempt to
>code, using Visual C++ 6....Here it goes:
>
>When encrypting most types of data, all the bits are shifted/reorganized..
>For example, when you encrypt a text file, you can view the encrypted
>contents on like Notepad or whatever, but say, if you are trying to encrypt
>a JPG or BMP file, you can't open it, because the header that delinates the
>file as a .JPG or .BMP file is also scrambled. I would like to try and have
>it so that If I encrypt a JPG or BMP file, that it is still viewable in a
>JPG or BMP viewer, but the actual picture contents are scrambled...so
>essentialy, you'd be opening a picture file with all the picture information
>viewable, but scrambled. Does anyone have any idea how I can go about doing
>this? Any ideas would be very much appreciated.
Decode the image into raw pixels, encrypt the pixels with a stream cypher
(RC4 would be a fine choice), then take the encrypted pixels and run them
back through the JPG/BMP/whatever encoding scheme to make a new image.
This sounds fairly simple, but rest assured that decoding and encoding
popular image formats is much more complicated than you'd like. There's
a lot of nuts and bolts stuff to be done here that is non-trivial. You've
just asked "I want to build a car." And I've just said, "Well hey, just
buy a frame, an engine, some wheels, and off you go!" In practice it
just ain't that easy. And then there's the crypto part, too. But hopefully
you'll be able to find free libraries on the net that will do both the
image and crypto stuff for you, so you'll mainly just have to glue it
all together. I know for a fact that the JPEG library exists, cause
I've played with it myself. I imagine you can buy RC4 libraries from
RSA data security. (Or just get a copy of _Applied Cryptography_ and
roll your own implementation.)
Word of warning, though - if you do this and you use JPGs, make
sure to set the JPG quality to 100% before encoding. JPG is a "lossy"
format - it loses detail in order to compress the image better. If the
encrypted pixels get altered this way, they will not decrypt correctly.
BMP and GIF (and TIFF and a lot of other "non-lossy" formats) don't have
this problem.
Another issue, more in the practical domain, is the problem of
decrypting the image. If you want someone to be able to view the image,
you're going to have to give them the crypto key used to encode it.
(Unless you store it in the image somewhere - in which case why did you
bother encrypting it?) This in turn implies that you have to keep a record
of what key goes with what image. On a small scale this is easy. On a large
scale it is a logistical nightmare. Also, once you let a key out, what's
to stop someone from copying it and giving away copies of it and the
image at the same time? Etc... But if you're just doing this for fun,
these kinds of problems probably aren't ones that you need to worry about.
-Ben
--
Ben Cantrick ([EMAIL PROTECTED]) | Yes, the BGC dubs still suck.
BGC Nukem: http://www.dim.com/~mackys/bgcnukem.html
The Spamdogs: http://www.dim.com/~mackys/spamdogs
"I'd rather know Lara Croft than Betty Crocker." -Douglas Copeland
------------------------------
From: Thomas Boschloo <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp,sci.math
Subject: Re: How to find a huge prime(1024 bit?)
Date: Tue, 27 Feb 2001 01:21:50 +0100
Jeremy Bishop wrote:
>
> Thomas Boschloo wrote:
>
> > If we skip the first successor of this new number P(1..x), we obviously
> > get a prime. The next however will be dividable by the prime number 2,
> > and the next by the also prime number 3, and the next will be dividable
> > by 4, etc. So in fact, I have proven that in the distribution of prime
>
> > BTW I now realize that P(1..x) can be written as x! (stupid me!)
>
> So are you saying that "x! + 1" is always prime?
I guess I did. F- for me on this topic :-(
But at least no-one would get hurt or killed if I stuck to programming
and making my PGP build a bit more inefficient. At least Lynn
Killingbeck calls it a 'common mis-statement' in his/her reply. That
makes me feel a little less unconfortable about my error.
I guess I should just not try to do any math when I am already sleepy.
And especially not formulate any 'definite' conclusions to continue on
the next day ;-) My first post was already in error.
TYA,
Thomas
--
Jessica "I'm not bad, I'm just drawn that way"
------------------------------
From: Thomas Boschloo <[EMAIL PROTECTED]>
Crossposted-To: comp.lang.ada
Subject: Re: Arcfour in Ada
Date: Tue, 27 Feb 2001 01:58:33 +0100
Julian Morrison wrote:
>
> "Thomas Boschloo" <[EMAIL PROTECTED]> wrote:
>
> > Why did you decide to go for arcfour and not the AES
> > http://www.nist.gov/aes ?
> > [...]
> >
> > AES seems so much more secure in the long run than RC4!
>
> AFAIK, the AES cypher is more secure in that you can safely reuse keys.
> It's also newer, though, and new crypto is less trustable. AES is also a
> very gread deal more CPU churn and overhead than Arcfour. Since you can
> only encrypt in blocks of four bytes, you need extraneous header info to
> show where the contents end, and you need to CBC the blocks together. If
> you're encrypting a lot of small things (such as in Fling's routeballs)
> the overheads will add up.
That makes sense. I believe you could perhaps use an escape character to
identify the end of a string. Like (and I have to dig deep into my
memory now) when you send a bit string, you could say that '000' marks
the end of your bit string. If you need to actualy send '000' you pad it
like '0010' or something like that. I am a bit rusty, have to look it up
in my old study books.
A better example might be the way printf and scanf work in C. '/' is the
escape character (like '/n', '/0', etc.) and if you actually want to
send a '/' you just send a '//'. It need not take up a lot of
bandwidth/space I think. But I don't know much about implementing TCP. I
do know that the freedom network stopped using fixed sized packages in
version 2.1 or something, because it took up too much bandwidth. I seem
to remember that they also use UDP for something but I am confusing
myself now. The good thing about UDP is that you don't have to set up a
connection to send data. It doesn't have to point back to you (which is
good if you want to be anonymous).
Well, who do I think I am :-) I'm sure you already know all you need to
know and more ;-)
Regards & Good luck,
Thomas
--
Jessica "I'm not bad, I'm just drawn that way"
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Improved stream cipher? (was: Re: Simple, possibly flawed, stream cipher)
Date: Tue, 27 Feb 2001 01:08:01 GMT
Henrick Hellstr�m wrote:
>
> Here is a similar cipher that shouldn't be vulnerable to Scott Fuhler's
> attack. These are the changes:
>
> * Instead of initializing x to 1, x is initialized to state[7].
If this is done, then we no longer can do hardware pipelining to one
clock per byte.
> * Instead of adding either 0 or 1 to state[i] depending on a single
> bit of x, x is added to state[i].
Hmm. Perhaps, but does it actually make analysis harder?
> * In order to prevent attacks that exploit differential relations on
> state[i], the state array is shifted up one byte and state[0] is set
> to the value of the cipher text.
Mixing in the ciphertext does not necessarily help, and may hurt,
especially if a chosen ciphertext attack is allowed.
In fact, we may even be able to find some [fixed!] chosen plaintext
which causes the cipher state to synchornize to some particular value,
or which will cause the exact state [or a trivially reversible transform
of it] to be outputed.
> I don't claim that this cipher is flawless. In fact, I hope someone
> will break it, since it in some respects is similar to Steak in
> design. (Yes, of course I have a hidden agenda. ;-))
--
A solution in hand is worth two in the book.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: ECC implementation
Date: Tue, 27 Feb 2001 01:12:42 GMT
Mike Rosing wrote:
>
> Michael Scott wrote:
> >
> > Its actually quite easy to test if the implementation is OK.
> > Generate a random point P on the curve and check that r.P=0, where r
> > is the number of points on the curve, and "0" is the point at
> > infinity.
>
> And if you don't know r for some arbitrary curve, you can check that
> P+P+P+P+P = 5*P. So you check your multiply routine with the addition
> routine. If they give the same answer, it worked. If not, you have
> a bug to find :-)
This will probably be better for testing, especially since I plan on
hardcoding a few large curves, and not doing searching for small curves.
--
A solution in hand is worth two in the book.
------------------------------
From: William Hugh Murray <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Super strong crypto
Date: Tue, 27 Feb 2001 01:16:42 GMT
wtshaw wrote:
> In article <[EMAIL PROTECTED]>, "Douglas A. Gwyn"
> <[EMAIL PROTECTED]> wrote:
>
> > As to key recovery, my working assumption is that we are
> > trying to figure out what form a realization of the subject
> > (super strong crypto) might take. *If* one has a basic
> > (e.g. block encipherment) component suitable for use in
> > such a scheme, then there is negligible chance that any
> > isolated key could be recovered. My straw man proposal
> > takes that as a starting place and build on it in an
> > attempt to avoid the obvious theoretical weakness of
> > stretching a small amount of key information over a long
> > span of encryption, as is often done in current (public)
> > systems. The suggestion is that something of the sort
> > might be a necessary component of any practical "super
> > strong crypto" system.
>
> Changing keys is like changing your underwear and socks, if they smell,
> you waited too long.
One is not likely to forget this analogy.
All other things equal, the more often one changes one's underwear, the less
likely it is to smell and the shorter the time that they will smell. However
all other things are never equal. The more often one changes, the more
underwear one must have and the less time one has for other things. Good
practice suggests that if you change once every day they will never smell for
too long.
> There are many ciphers with an unknown threshold for safe ciphertext under
> a specific key. For those, it's still good to periodically change keys as
> good security policy; for those with a definite threshold, usually all too
> short, changing keys may merely mean isolating messages, requiring brute
> forcing of each individual message.
All other things equal, the fewer keys one uses, the lower the cost of attack
and the greater the cost of attack. All other things equal, the more keys one
uses the higher the cost of attack to an adversary and the lower the value of
success. For a given amount of data, as the number of keys increases, the
cost of attack approaches infinity and the value of success approaches zero.
Said the other way, the more information that is encrypted under a single key,
the more information about that key is leaked and the more information is
leaked if the key is compromised. However, as with underwear, there are
limits and costs. Therefore, good practice for keys says that if one changes
the key once for every object, e.g., file, message, connection, one will not
lose too much or spend too much.
In its proposal to the IETF for key management for secureIP, IBM recommends
changing keys periodically during a persistent connection. They suggest that
one run multiple logical channels, one for traffic and one for negotiating new
keys.
>
> --
> Better to pardon hundreds of guilty people than execute one
> that is innocent.
------------------------------
From: William Hugh Murray <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: "RSA vs. One-time-pad" or "the perfect enryption"
Date: Tue, 27 Feb 2001 01:22:50 GMT
Simon Johnson wrote:
> Douglas A. Gwyn <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > William Hugh Murray wrote:
> > > Modern cryptography is not provable or perfect. However, it is
> > > demonstrably, as opposed to provably, good enough, as opposed to
> > > perfect.
> >
> > I would like to see such a demonstration. What threat model
> > are you assuming, against high school hackers?
>
> Actually, that isn't such a bad threat model.
I love it. You must be a security person.
------------------------------
From: [EMAIL PROTECTED] (Larry Kilgallen)
Crossposted-To: comp.lang.ada
Subject: Re: Arcfour in Ada
Date: 26 Feb 2001 20:39:47 -0500
In article <[EMAIL PROTECTED]>, Thomas Boschloo <[EMAIL PROTECTED]>
writes:
> Why did you decide to go for arcfour and not the AES
> http://www.nist.gov/aes ? AFAIK Arcfour or RC4 was originally a
> 'security by obscurity' cypher (Arcfour was (now illegal) reverse
> engineered from RC4 by www.rsa.com).
Regardless of the merits of various algorithms, it helps to use the same
algorithm as the person with whom you are trying to communicate. RC4 is
present in several widely used applications.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Am I doing something silly by including my gnupghome with my
Date: Tue, 27 Feb 2001 02:15:09 GMT
jtnews wrote:
>
> Paul Rubin wrote:
> >
> > jtnews <[EMAIL PROTECTED]> writes:
> > > I'm making CD-RW disks with encrypted archives
> > > of my work with an unencrypted gnupghome
> > > directory on it.
> >
> > This doesn't seem like a wise idea unless you're sure your passphrase
> > is long enough to not be guessable by brute force. I'm assuming you're
> > leaving copies of the discs off-site which means other people might
> > access them.
> >
> > If you're trying to protect the key long-term, the passphrase should
> > have at least 90 bits of entropy. So if it's a Diceware password
> > (www.diceware.com), for example, it should be 7 or more words long.
> >
> > http://www.nightsong.com/crypto/dice.php gives you 5-word Dice
> > passphrases, so you could generate two such phrases (giving 10
> > words) and use 7 (or more) of the words.
> >
> > Really though, your safest bet is to encrypt the entire disc with a
> > long passphrase of the above type.
> >
> > For more about backups, see www.taobackup.com.
>
> The web site is nice. But how do I know
> the site isn't recording every passphrase
> it's generating, and then logging my IP address
> so that someone can try to monitor what I'm
> doing and try to break into my accounts?
Because can you supply your own entropy, and the password generation is
done client-side, with javascript. There *is* a server-supplied
"random" string, which they could, concievably, be recording, but if you
supply enough randomness in the textarea, you don't have to worry about
that fact.
You can look at the javascript source and see for yourself what is
happening when it generates the passphrase.
--
A solution in hand is worth two in the book.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Am I doing something silly by including my gnupghome with my
Date: Tue, 27 Feb 2001 02:34:24 GMT
jtnews wrote:
>
> Paul Rubin wrote:
> >
> > jtnews <[EMAIL PROTECTED]> writes:
> > > I'm making CD-RW disks with encrypted archives
> > > of my work with an unencrypted gnupghome
> > > directory on it.
> >
> > This doesn't seem like a wise idea unless you're sure your
> > passphrase is long enough to not be guessable by brute force. I'm
> > assuming you're leaving copies of the discs off-site which means
> > other people might access them.
> >
> > If you're trying to protect the key long-term, the passphrase should
> > have at least 90 bits of entropy. So if it's a Diceware password
> > (www.diceware.com), for example, it should be 7 or more words long.
> >
> > http://www.nightsong.com/crypto/dice.php gives you 5-word Dice
> > passphrases, so you could generate two such phrases (giving 10
> > words) and use 7 (or more) of the words.
> >
> > Really though, your safest bet is to encrypt the entire disc with a
> > long passphrase of the above type.
> >
> > For more about backups, see www.taobackup.com.
>
> Incidentally, one of the reasons why
> I was looking for passphrases based
> on transcendental numbers is that
> such passphrases can be made very long,
> while being easy to remember because they
> can be expressed as relatively
> simple mathematical expressions.
But they only have as much entropy as that mathematical expression does,
so there's no advantage to using (the first x digits of the
transcendental between 4 and 5) as opposed to ("4, 5"). The second is
just as hard, or just as easy, to guess as the first.
> My biggest fear is inventing a long passphrase
> for an encrypted backup, only to have the backup
> become worthless because I forgot the passphrase!
> I could write it down, but then that would defeat
> the purpose of the passphrase to begin with!
Contrary to historical opinion, writing down the passphrase does NOT
decrease the strength of the system. It's writing it down and allowing
it to be stolen which breaks the system. There is no harm in writing it
down and storing it with your credit cards -- especially if the value of
the data protected by the passphrase is no more than the max spending
limit on your cards :)
IIRC, The "common" belief that passwords should never be written down
comes from military security -- where if *one* person forgets the
password, all is not lost; there are usually others who know it.
Data security is not the same as military identification/authorization
security. If you forget the password, that's generally it. Most
likely, noone else is going to know it. All is lost if the password is
lost.
So ask yourself -- which is a greater (more likely) risk, someone
stealing your wallet, or you forgetting your passphrase and losing all
that data?
--
A solution in hand is worth two in the book.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: The Key Vanishes: Scientist Outlines Unbreakable Code, Read it and Weep
Boys
Date: 26 Feb 2001 18:16:37 -0800
"Mxsmanic" <[EMAIL PROTECTED]> writes:
> 1. You need lots of bits in order to prevent anyone from recording them
> all. Where are you going to find a source of hundreds of terabits of
> perfectly random data per second?
You may not need this much data. Fiber optic systems have been
demonstrated at close to a terabit per second.
> 2. In order to be completely secure, only one message can be encrypted
> with the key stream at a time. What if you find two messages encrypted
> with it? Cracking an OTP is trivial if the key is used more than once.
> Keep in mind that the two messages need not start with the same bit; if
> their key streams overlap anywhere, you can crack that part of the
> ciphertext.
It's true that the papers in the literature don't discuss what happens
if two people use the same data stream. But it's probably still okay.
You are mistaken to think that you just index into the data stream and
use it for a OTP. Rather, the communicators share a PRNG which
indexes randomly into the data stream, and these bits are then xored
together to form the OTP. This means that different groups can use
the same data stream and have completely different pads.
> 3. Since the only secret key in this algorithm is the starting point in
> the stream, and since one must assume that any public portion of an
> algorithm is known to all in its entirety, one must assume that all the
> security of this algorithm resides in the secret key that gives the
> starting point of the random bit stream to use for encryption (and
> decryption).
True, except the secret key does not determine only the starting
point, but also how the bits are selected and skipped and xored
together to form the OTP.
> If that starting point could be chosen anywhere in all of
> eternity, blah blah blah, 80 bits of security, blah blah...
I suggest you read the Maurer paper in Crypto 97 and the Rabin in Crypto 99
and you will learn more about how these systems work.
> 4. Who would implement and pay for such a system, and why would he make
> it available to everyone for free?
He'll just encrypt the bits and charge for the decryption key... ;-)
Alpha
------------------------------
** 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
******************************
