Cryptography-Digest Digest #397, Volume #13 Thu, 28 Dec 00 07:13:00 EST
Contents:
Re: Possible AONT? (Benjamin Goldberg)
Re: polynomial permutation cipher (Benjamin Goldberg)
Re: MD5 and hash127 questions ([EMAIL PROTECTED])
Re: Quick CRT question: (Bryan Olson)
Re: "Content Protection for Recordable Media" (Vernon Schryver)
Re: Quick CRT question: ("Peter L. Montgomery")
Re: Merry Christmas (Dennis Ritchie)
Re: Quick CRT question: ("Matt Timmermans")
Re: What's better CAST in PGP or Blowfish 128bit? ("Tom ST Denis")
Identifying string with blowfish (Christian =?iso-8859-1?Q?Reitwie=DFner?=)
Basic infor for newbies ("Dullboy")
Basic infor for newbies ("Dullboy")
Basic infor for newbies ("Dullboy")
Basic infor for newbies ("Dullboy")
Basic infor for newbies ("Dullboy")
Basic infor for newbies ("Dullboy")
Re: Identifying string with blowfish (Paul Rubin)
----------------------------------------------------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Possible AONT?
Date: Thu, 28 Dec 2000 04:23:51 GMT
David Hopwood wrote:
>
> -----BEGIN PGP SIGNED MESSAGE-----
>
> Benjamin Goldberg wrote:
> > This AONT idea is based very much on the recent thread about order
> > 32 irreducible GF(2)[x] polynomials.
> >
> > The security of this is depends on both a 32 bit keyed permutation
> > generator, E,
>
> What assumption are you making about E? (Actually it doesn't really
> matter because the scheme has weaknesses even if E is a perfect PRP.)
For the purposes of proof security (or lack thereof), I'm assuming E is
a random oracle that takes sizeof(k) bits as input, and has as an output
a permutation E_k, which is randomly selected from the just less than
2^27! permutations which have the irreducible polys in different orders.
> > and a secure hash function, H.
> >
> > The transform is as follows:
> > k = (hash output size) random bytes
> > counter = 0
> > repeat (filelength/4) times
> > do {
> > poly = E_k( counter )
> > counter = counter + 1;
> > } until( irreducible( poly ) );
> > crcval = crc( file, poly );
> > output( crcval );
> > H.add( crcval );
> > end repeat
> > output( H.result() XOR k );
> >
> > Reversing the transform is done using CRT.
> >
> > Any comments?
>
> It is obviously not secure according to the definition of a
> computationally-secure AONT in [1] or [2]. Even the first word of
> output gives a non-negligable amount of information about the file
> (since there are less than 2^32 irreducible 32-bit polys, some
> input files are impossible for a given output).
There are approximately 2^27 irreducible order-32 polys. If the message
is more than a few (2 or 3) 32-bit words, and significantly less than
2^27, and padded with a 1 as the MSB, then it should take O(2^27) work
to rule out a possible file based on any particular word of the output.
Although 2^27 is a very small amount of work, it *is* brute force that
needs to be done. Suppose for an instant that someone could brute force
128 bits. Then, one could find out the contents of a file with OAEP
that has any number of bytes missing -- just brute force the key to the
stream cipher, and all the information becomes visible.
With this system, it could easily be expanded to require near 2^128
effort for brute force -- use bigger polynomials, and of course a bigger
permutation generator. Suppose I used Rijndael with 256 bit blocksize
as my permutation generator. If there are at least 2^128 different
order-128 irreducible polynomials, then it takes at least 2^128 work at
brute force to use one "word" to rule out a particular file.
> [Can I have a general whinge that people should not try to design
> AONTs unless they understand what an AONT is, and in particular how
> strict the definition of that term is? There have been several
> instances of this recently on sci.crypt.]
>
> [1] Victor Boyko,
> "On All-or-Nothing Transforms and Password-Authenticated Key
> Exchange Protocols,"
> PhD Thesis, MIT, June 2000.
> (should be somewhere at http://www.toc.lcs.mit.edu/~boyko/, but
> that seems to be down at the moment)
>
> [2] Yevgeniy Dodis,
> "Exposure-Resilient Cryptography,"
> PhD Thesis, MIT, August 2000.
> http://www.toc.lcs.mit.edu/~yevgen/ps/phd-thesis.ps
Both seem to be down.
By the way, if OAEP is used with a smaller (say, 32 bit) hash and key,
does it cease to be an AONT?
--
Power interrupts. Uninterruptable power interrupts absolutely.
[Stolen from Vincent Seifert's web page]
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: polynomial permutation cipher
Date: Thu, 28 Dec 2000 04:34:50 GMT
Mok-Kong Shen wrote:
>
> Benjamin Goldberg wrote:
> >
> > Mok-Kong Shen wrote:
> > >
> > > Benjamin Goldberg wrote:
> > > >
> > > [snip]
> > > > Here's a simple example:
> > > > pt = a 128 bit value, or a poly of order at most 127
> > > > ct[0..3] = each is a 32 bit value, or a poly of order at most 31
> > > > py[0..3] = each is a different irreducible order-32 poly
> > > > % = GF(2)[x] polynomial remainder (aka crc)
> > > > * = GF(2)[x] polynomial multiplication
> > > > + = GF(2)[x] polynomial addition (aka XOR)
> > > >
> > > > To encrypt, we take the crcs:
> > > > for i in 0..3
> > > > ct[i] = ( pt + x^128 ) % py[i];
> > > >
> > > > To decrypt, we use the CRT algorithm:
> > > > pt = ct[0] * py[1] * py[2] * py[3] +
> > > > ct[1] * py[0] * py[2] * py[3] +
> > > > ct[2] * py[0] * py[1] * py[3] +
> > > > ct[3] * py[0] * py[1] * py[2] +
> > > > py[0] * py[1] * py[2] * py[3] + x^128;
> > > >
> > > > See? Lots of multiplications, but no inversions.
> > >
> > > I am certainly confused. But from the last equation,
> > > one obtains
> > >
> > > ( pt + x^128) % py[0] =
> > >
> > > ct[0] * py[1] * py[2] * py[3] % py[0]
> > >
> > > How could one show that this is identical to ct[0]?
> >
> > Let t[0..3] be temp variables, and ignore for the moment the x^128
> > term.
> > t[0] = ct[0] * py[1] * py[2] * py[3]
> > Consider t[0] % py[1,2,3]. Since t[0] is a product of each poly,
> > the remainder modulo any of them is 0. Now consider t[0] % py[0].
> > Since t[0] is a multiple of ct[0], t[0] % py[0] == ct[0] % py[0].
> >
> > These relationships hold true for all t[i].
>
> But we have to show t[0] % py[0] == ct[0] !!
>
> Please note in the equation I gave that the left hand side
> is by definition ct[0] (according to your encrption part)
> and the right hand side is computed using the equation you
> gave in the decryption part, so this right hand side should
> be identical to ct[0]. (Else please kindly point out which
> point of my argument is erroneous.)
I'm confused. What do you want me to explain? It looks like you've
already answered your own question.
If you don't understand why CRT works, please read a paper or two on it,
there are surely some on the web. I don't recall any offhand, but I'm
sure you can use a search engine just as well as I.
--
Power interrupts. Uninterruptable power interrupts absolutely.
[Stolen from Vincent Seifert's web page]
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: MD5 and hash127 questions
Date: Thu, 28 Dec 2000 05:14:03 GMT
10x alot.
Merry Cristmas and Happy New Year to all members of group and their
families.
Best Regards,
Stoyan
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Quick CRT question:
Date: Thu, 28 Dec 2000 06:02:12 GMT
Benjamin Goldberg wrote:
> Does anyone know if it's possible to use CRT in less than P(N^3) time,
> where N is the number of (modulo, remainder) tuples?
Yes. In fact I just posted both a reference and code for
Garner's algorithm for CRT reconstruction in the thread
"polynomial permutation cipher", (which may not have
reached your server yet).
--Bryan
Sent via Deja.com
http://www.deja.com/
------------------------------
From: [EMAIL PROTECTED] (Vernon Schryver)
Subject: Re: "Content Protection for Recordable Media"
Date: 27 Dec 2000 23:41:19 -0700
In article <[EMAIL PROTECTED]>,
David Hopwood <[EMAIL PROTECTED]> wrote:
>This has to be stamped on at least as hard as the PIII processor ID
>was (it is actually a *much* more disruptive and dangerous misfeature).
>
>http://www.theregister.co.uk/content/2/15620.html
> ...
Nonsense. The PIII processor ID provided nothing that was not already
old and familiar. At most, it would have provided a nice a handle for
"node locking" software to machines that don't have Ethernet cards. Every
conscious reader of this newsgroup intuitively understands that thanks to
the birthday paradox value, generating a random 128 value with local
sources of randomness is just as useful and almost as handy as a quick
sequence of instructions for fetching a hardware chassis serial number
such has been standard on most machines bigger than PC's since the 1980's.
The noise about the PIII ID assumed that Intel and Microsoft would control
all code that might ever run on PC's and everyone would be run noisy snoopy
software that would blab a new WIN32 GUID based on the PIII ID instead of
continuing to blab the old and still existing WIN32 GUID. The only people
who found the PIII story interesting were some Intel salescritters and a
bunch of willfully ignorant people unwilling to extert themselves enoough
to notice and worry about real dangers to privacy.
Instead of running around and screaming about this latest excitement and
only later thinking, let's think first and scream only if it makes sense.
- Would you still be able to write any sequence of bits you wanted
to one of these drives?
- having written your data, would you be able to read it?
- a computer that wouldn't let you copy your data to other computers on
a network would be kind of limited, so who would buy one?
- how would this stuff prevent you from copying your data among your
disks or giving it to your friends? Could you copy your bits from your
evil disk to a DVD, CDROM, or even a floppy? You might not be able to
trade hard drives, but do you do that now? (I've done that plenty
with those "cartridges" for SCSI and IDE, but most people don't.)
- You might not be able to do what some kinds of what were once called
image backups, but most people don't do any backups.
- is this stuff supposed to stop you from violating copyrights?
If the copyright owners want you to pay them to use their bits, you
must be able to must be able to read and fondle the bits as cleartext,
just as your DVD player must be able to generate pixels and your music
player must be able make sounds. Couldn't you always point a video
camera at your monitor or TV and generate bits no matter what the evil
Hollywood moguls say?
Thus, the only thing this stuff can protect is the compression of the
data, and even that not very well. At worst you'll have to spend your
own resources to compress it to fit 2 hours of NTSC or better video on
the DVD's you'll burn. Today that might be an issue, but will it still
be by the time this nonsense could be common in the market?
No, this is just a typical consortium brain fart. The only people
who pay attention to such drek are those who've not lived though a
few such clouds and those who make their livings spreading them, from
the professional consortium flaks inside the hotel ballrooms to the
trade rag consultants and would be populist politicians.
Vernon Schryver [EMAIL PROTECTED]
------------------------------
From: "Peter L. Montgomery" <[EMAIL PROTECTED]>
Subject: Re: Quick CRT question:
Date: Thu, 28 Dec 2000 07:10:53 GMT
In article <[EMAIL PROTECTED]>
Benjamin Goldberg <[EMAIL PROTECTED]> writes:
>Does anyone know if it's possible to use CRT in less than P(N^3) time,
>where N is the number of (modulo,remainder) tuples?
>Assume all modulo are irreducible GF(2)[x] polynomials of the exact same
>order, and assume that we don't have to check for duplicates.
>Or, equivilantly, all modulo are prime (or at least relatively prime)
>integers, and all have the exact same number of bits.
I'll assume you're using the same moduli repeatedly, so
setup time (to compute constants) is unimportant.
Suppose the moduli are m_1, m_2, ..., m_N
and M = m_1 * m_2 * ... * m_N is their product.
Pre-compute c_i == (M/m_i)^(-1) mod m_i.
Given remainders r_1 mod m_1, ..., r_n mod m_N, let
R = sum_i (r_i * c_i mod m_i) * (M / m_i)
The 0 <= R < N*M and R == r_i mod m_i for all i.
Getting R takes N modular multiplications,
N (length-1)*(length N-1) multiplications, and
N (length-N) additions. Reducing the sum modulo M
takes at most N subtractions of M.
This straightforward method takes O(N^2) steps.
--
Can't decide between Gore and Bush? Elect them both.
A Gore-Bush-ship sounds like Gorbachev.
[EMAIL PROTECTED] Home: San Rafael, California
Microsoft Research and CWI
------------------------------
From: Dennis Ritchie <[EMAIL PROTECTED]>
Subject: Re: Merry Christmas
Date: Thu, 28 Dec 2000 07:22:32 +0000
David A Molnar wrote:
...
> That being said, happy holidays!
> (and a crypto question: what does Santa use to keep his list of
> "naughty" and "nice" children private? how does he look up a kid in the
> database?)
The oldie (from the Brahms Gang at Berkeley):
obnoxio@brahms (weemba) wrote [in netnews long ago]--
better !pout !cry
better watchout
lpr why
santa claus <north pole >town
cat /etc/passwd >list
ncheck list
ncheck list
cat list | grep naughty >nogiftlist
cat list | grep nice >giftlist
santa claus <north pole > town
who | grep sleeping
who | grep awake
who | grep bad || good
for (goodness sake) {
be good
}
These days I would trust Santa uses an encrypted disk partition.
Dennis
------------------------------
From: "Matt Timmermans" <[EMAIL PROTECTED]>
Subject: Re: Quick CRT question:
Date: Thu, 28 Dec 2000 07:53:50 GMT
Haven't seen Bryan's post yet, but the almost-naive (i.e., easy) way takes
N^2 time too:
Multiply all the moduli (q_i) together to get Q (O(N^2))
For each q_i, calculate Q_i = (Q/q_i) (O(N^2) altogether)
For each Q_i and remainder r_i, calculate a_i | a_i*Q_i = r_i mod q_i (
O(N^2) altogether -- do Q_i mod q_i first)
result is the sum of all a_i*Q_i (O(N^2))
"Bryan Olson" <[EMAIL PROTECTED]> wrote in message
news:92el13$lmc$[EMAIL PROTECTED]...
> Benjamin Goldberg wrote:
> > Does anyone know if it's possible to use CRT in less than P(N^3) time,
> > where N is the number of (modulo, remainder) tuples?
>
> Yes. In fact I just posted both a reference and code for
> Garner's algorithm for CRT reconstruction in the thread
> "polynomial permutation cipher", (which may not have
> reached your server yet).
------------------------------
From: "Tom ST Denis" <[EMAIL PROTECTED]>
Subject: Re: What's better CAST in PGP or Blowfish 128bit?
Date: Thu, 28 Dec 2000 08:31:37 GMT
"Darryl Wagoner - WA1GON" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> [EMAIL PROTECTED] (Tom St Denis) wrote in
<90tp0u$nko$[EMAIL PROTECTED]>:
>
> >I would trust a "secure application" written by a real cryptographer.
> >Just because "heart transplants" exist doesn't mean a IT specialist can
> >perform them right?
>
> So mean if a good software engineer that isn't a cryptographer
> can't be trusted to create a secure application? This is type
> of attitudes that creates the mystique that this is a black
> art.
Often security holes are things people just don't think about. You need the
right mindset to be a good security application developer. If you are
careless (i.e work for microsoft) lots of problems will be exploited.
Tom
------------------------------
From: [EMAIL PROTECTED] (Christian =?iso-8859-1?Q?Reitwie=DFner?=)
Subject: Identifying string with blowfish
Date: Thu, 28 Dec 2000 12:11:41 +0100
Hi!
I wrote blowfish-encryption for IRC. But when the program decrypts a message,
it doesn't know if the key is correct and what comes out is crap. So I want to
add some identifier that makes clear that the message was decrypted correctly.
I thought of some spaces or a constant word that will always be at the
beginning of the message.
The second method is the key itself being encrypted with the message at the
front.
And the third is a checksum of the message.
What is the securest of these three methods, or can you think of something
else?
CU
Christian
--
Christian Reitwie�ner <[EMAIL PROTECTED]>
--> http://www.secretstar.de
Kenny the talking bot:
--> kenny_dod #frg on IRCNet
------------------------------
From: "Dullboy" <[EMAIL PROTECTED]>
Subject: Basic infor for newbies
Date: Thu, 28 Dec 2000 12:35:21 +0100
I recently got interested in cryptology reading a book on the subject and
was wondering where I can find more information in general and in specific
crypto methods. Are there any sites that are more relevant than others?
Thanks /Fredrik
------------------------------
From: "Dullboy" <[EMAIL PROTECTED]>
Subject: Basic infor for newbies
Date: Thu, 28 Dec 2000 12:35:38 +0100
I recently got interested in cryptology reading a book on the subject and
was wondering where I can find more information in general and in specific
crypto methods. Are there any sites that are more relevant than others?
Thanks /Fredrik
------------------------------
From: "Dullboy" <[EMAIL PROTECTED]>
Subject: Basic infor for newbies
Date: Thu, 28 Dec 2000 12:35:21 +0100
I recently got interested in cryptology reading a book on the subject and
was wondering where I can find more information in general and in specific
crypto methods. Are there any sites that are more relevant than others?
Thanks /Fredrik
------------------------------
From: "Dullboy" <[EMAIL PROTECTED]>
Subject: Basic infor for newbies
Date: Thu, 28 Dec 2000 12:35:38 +0100
I recently got interested in cryptology reading a book on the subject and
was wondering where I can find more information in general and in specific
crypto methods. Are there any sites that are more relevant than others?
Thanks /Fredrik
------------------------------
From: "Dullboy" <[EMAIL PROTECTED]>
Subject: Basic infor for newbies
Date: Thu, 28 Dec 2000 12:35:46 +0100
I recently got interested in cryptology reading a book on the subject and
was wondering where I can find more information in general and in specific
crypto methods. Are there any sites that are more relevant than others?
Thanks /Fredrik
------------------------------
From: "Dullboy" <[EMAIL PROTECTED]>
Subject: Basic infor for newbies
Date: Thu, 28 Dec 2000 12:35:46 +0100
I recently got interested in cryptology reading a book on the subject and
was wondering where I can find more information in general and in specific
crypto methods. Are there any sites that are more relevant than others?
Thanks /Fredrik
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: Identifying string with blowfish
Date: 28 Dec 2000 04:06:21 -0800
[EMAIL PROTECTED] (Christian Reitwie�ner) writes:
> I wrote blowfish-encryption for IRC. But when the program decrypts a
> message, it doesn't know if the key is correct and what comes out is
> crap. So I want to add some identifier that makes clear that the
> message was decrypted correctly. I thought of some spaces or a
> constant word that will always be at the beginning of the message.
> The second method is the key itself being encrypted with the message
> at the front. And the third is a checksum of the message.
>
> What is the securest of these three methods, or can you think of something
> else?
The first method (constant word) will protect against accidentally
using the wrong key, but won't protect against the message being
tampered with by an active attacker.
The second method is no good because 1) it's always bad to leak info
about the key; 2) in some systems the key may not be available (i.e.
you can encrypt and decrypt with it but not access it directly).
You could, however, use a cryptographic hash of the key.
The third method is the best: attach a checksum of the message to the
message, before encryption. Then encrypt the whole resulting string
(so both the message and the checksum are encrypted).
Finally you can use a combination of all three methods (or a subset):
1) a constant word or byte to identify the algorithm (but not the key).
2) cryptographic hash of the key, so if the receiver has several keys
in storage, s/he can choose the right one
3) checksum of the message, under the encryption.
------------------------------
** 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
******************************
