Cryptography-Digest Digest #399, Volume #13 Thu, 28 Dec 00 18:13:01 EST
Contents:
Re: polynomial permutation cipher (Mok-Kong Shen)
Re: Foolproof Quantum Cryptography (Tim Tyler)
I may file a complaint with the FBI against some people in the past and corporations
such as Nokia .... .. these charges I file shall be industrial espionage changes
(Markku J. Saarelainen)
Re: Windows 98 desktop lockdown application (Simon Johnson)
Re: example code for your use (*Sacrificial Lamb* (Serge ))
Re: "Content Protection for Recordable Media" (Mok-Kong Shen)
Re: Random keys of arbitrary length ("Joseph Ashwood")
Re: Quick CRT question: (Bryan Olson)
Re: comparison of ciphers' speed (Paul Rubin)
Re: comparison of ciphers' speed ("Joseph Ashwood")
Re: Quick CRT question: ("Matt Timmermans")
Basic infor for newbies ("Dullboy")
Basic infor for newbies ("Dullboy")
Re: "Content Protection for Recordable Media" (nobody)
Re: Random keys of arbitrary length (Simon Johnson)
Re: "Content Protection for Recordable Media" (John Savard)
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: polynomial permutation cipher
Date: Thu, 28 Dec 2000 19:12:23 +0100
Benjamin Goldberg wrote:
>
> 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.
I meant you are wrong with your encryption/decryption.
I explained an equation derived from your stuff which
cannot be true for arbitrary four polynomials in your
example. For it would mean
ct[0] == ct[0] * py[1] * py[2] * py[3] % py[0]
See also the follow-up of Bryan Olson. (BTW, I imagine
that I understand CRT.)
M. K. Shen
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Foolproof Quantum Cryptography
Reply-To: [EMAIL PROTECTED]
Date: Thu, 28 Dec 2000 18:06:17 GMT
Tim Tyler <[EMAIL PROTECTED]> wrote:
: There are also MITM attacks involving the side channel to consider, if
: this is not properly authenticated.
Apologies - this was a severely non-standard use of "side channel" on my part.
I meant to refer to what is often popularly described as "the telephone call".
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Hat: Baldness cure.
------------------------------
From: Markku J. Saarelainen <[EMAIL PROTECTED]>
Crossposted-To: alt.2600,alt.security,comp.security
Subject: I may file a complaint with the FBI against some people in the past and
corporations such as Nokia .... .. these charges I file shall be industrial espionage
changes
Date: Thu, 28 Dec 2000 18:19:44 GMT
Actually I never drunk anything, but they wanted to go to Joensuu in
Finland to celebrate ... I was a driver ... one was a police officer
with an advanced electrical training, two others worked for Nokia in
cellphones ... Tampere ...
Just wondering if Nokia and other people are somehow involved in
privacy violations in the U.S.A. ... in 1998 Jimmy from 99x called me
and left a message to me to win a prize .. at the same time there was a
round trip to Finland advertised by Nokia in the same radio station ...
well if they violated my privacy, they also commited the crime of
industrial espionage, because I was the business man / consultant ...
and they broke the Eeconomic Espionage Act of 1996 of the U.S.A. which
is the Federal Crime and fall under the jurisdiction of the FBI ... so
this is the way it is .....
I may contact the FBI and file charges .. so this is the way it will
be ...
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Simon Johnson <[EMAIL PROTECTED]>
Subject: Re: Windows 98 desktop lockdown application
Date: Thu, 28 Dec 2000 18:15:11 GMT
In article <92fkne$c77$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Hello,
>
> I have a Windows 98 desktop that is shared by many people in a lab.
>
> Is there a way that I can create a base installation (operating system
> plus applications) and have that boot every time? That way, if the
user
> make changes to the desktop, registry, etc., it will always boot into
> the base configuration.
>
> Thanks!
>
> Brian
>
> Sent via Deja.com
> http://www.deja.com/
>
Two ways. First record all the changes the user makes during their use
of the machine, then on reboot make a program the reverses it all.
Or, have a disk-image on some other drive and have it extract over the
other drive on boot, then start up that partition.
Not sure if these programs exist though.
Simon
--
Hi, i'm the signuture virus,
help me spread by copying me into Signiture File
Sent via Deja.com
http://www.deja.com/
------------------------------
Subject: Re: example code for your use
From: [EMAIL PROTECTED] (*Sacrificial Lamb* (Serge ))
Reply-To: [EMAIL PROTECTED]
Crossposted-To: comp.lang.c,comp.lang.c.moderated
Date: 28 Dec 2000 18:35:55 GMT
Da Big Book quoteth on 03 Nov 2000 23:00:27 GMT, famous Monk
[EMAIL PROTECTED] (Kenneth Lantrip) preached:
> I have written a nice (I think so) little program in C to help me learn the use
> of the language. I'm not sure if it's legal to post an encryption algorithm
> that uses a 128 bit key. I'd like to offer it to whoever wants to see the code
> so that they might can use parts of it or learn from it or whatever.
[snip]
I'd be interrested out of curiosity :)
however... I live in Europe.
> If you would like to look over the source code, e-mail me and I'll send it to
> ya if ya live in the USA. I'm not sure export laws allow 128 bit crypto
> algorithms to be exported. However, I can point you in the right direction to
> where you can get the source for the IDEA algorithm that was used in the
> program below. I can still send you the main() function.
[snip]
point ahead :)
I don't know if it's still forbidden, but you could just as well
modify your program and have an "international 40 bits" version...
once one has the code, getting it from 128 to 40 to 128 bits shouldn't
be too complicated :)
As someone pointed however, you might indicate/document for which
computer (I'd guess at a PC) and OS and compiler it's meant.
> I realize that these stupid crypto laws are a direct infringement of my first
> amendment constitutional right!
How about ours :) [not that onyone cares]
Serge
==============================================================================
The opinions expressed are mine and none other's
==============================================================================
Serge Marelli
[EMAIL PROTECTED]
--
comp.lang.c.moderated - moderation address: [EMAIL PROTECTED]
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: "Content Protection for Recordable Media"
Date: Thu, 28 Dec 2000 20:23:07 +0100
David Hopwood wrote:
>
> Stealth plan puts copy protection into every hard drive
> By: Andrew Orlowski in San Francisco
> Posted: 20/12/2000 at 18:54 GMT
>
> Hastening a rapid demise for the free copying of digital media, the next
> generation of hard disks is likely to come with copyright protection
> countermeasures built in.
[snip]
Dumb quesion: What prevents one from reading from such a
drive into memory and writing out to a drive without
protection features, which some manufacturers of the world
would certainly continue to produce to meet a corresponding
market demand?
M. K. Shen
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Random keys of arbitrary length
Date: Thu, 28 Dec 2000 11:21:14 -0800
Just a suggestion since it seems reasonable in many contexts to burn cycles
generating random keys, what I would suggest is that you start an extra
thread (as low priority as possble), that thread simply pumps bytes out of
RC4. It's a very tiny entropy gathering tool, over the course of a day
you'll probably add a couple bits.
You might also look into using something along the lines of Yarrow
(www.counterpane.com) that would improve the security much more.
Joe
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Quick CRT question:
Date: Thu, 28 Dec 2000 19:27:06 GMT
Matt Timmermans wrote:
[...]
> 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))
That sum can be larger than Q (even if we add the requirement
on a_i that 0 <= a_i < q_i), so we need mod Q at the end. It
still runs in O(n^2).
--Bryan
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: comparison of ciphers' speed
Date: 28 Dec 2000 12:26:42 -0800
Here's OpenSSL on a 667 mhz Celeron:
The 'numbers' are in 1000s of bytes per second processed.
type 8 bytes 64 bytes 256 bytes 1024 bytes 8192 bytes
md2 0.00 0.00 0.00 0.00 0.00
mdc2 0.00 0.00 0.00 0.00 0.00
md5 6824.17k 37131.07k 75700.22k 100739.16k 108565.85k
hmac(md5) 2934.70k 19423.54k 51005.28k 86416.29k 105542.26k
sha1 4442.90k 21106.30k 38905.80k 48885.54k 52789.80k
rmd160 3650.41k 17029.93k 30001.79k 37307.85k 40185.08k
rc4 52030.85k 69586.12k 75125.99k 74645.30k 75723.56k
des cbc 13771.68k 15503.23k 15583.07k 15518.08k 15870.56k
des ede3 5286.93k 5450.64k 5542.75k 5545.64k 5556.91k
idea cbc 0.00 0.00 0.00 0.00 0.00
rc2 cbc 5171.55k 5568.79k 5621.25k 5642.92k 5630.60k
rc5-32/12 cbc 0.00 0.00 0.00 0.00 0.00
blowfish cbc 20118.09k 23074.53k 23659.85k 23808.86k 23770.68k
cast cbc 20004.69k 22847.57k 23532.44k 23333.72k 23250.34k
sign verify sign/s verify/s
rsa 512 bits 0.0018s 0.0002s 557.9 5406.6
rsa 1024 bits 0.0097s 0.0005s 103.1 1825.2
rsa 2048 bits 0.0596s 0.0018s 16.8 544.1
rsa 4096 bits 0.4092s 0.0065s 2.4 153.8
sign verify sign/s verify/s
dsa 512 bits 0.0018s 0.0022s 552.1 464.5
dsa 1024 bits 0.0052s 0.0064s 192.2 155.8
dsa 2048 bits 0.0174s 0.0214s 57.5 46.8
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: comparison of ciphers' speed
Date: Thu, 28 Dec 2000 12:57:42 -0800
At http://www.eskimo.com/~weidai/benchmarks.html you'll find the benchmarks
that get quoted here the most.
Joe
"maciek" <[EMAIL PROTECTED]> wrote in message news:92fp73$efp$[EMAIL PROTECTED]...
> I checked common cipher algorithms for their speed. I used demo program
> from Delphi Encryption Compendium by Hagen Reddmann. My question is
whether
> this results are proportional. What I mean is that the implementation in
> Delphi might not be the fastest one but I need to know if there are no
huge
> disproportions beetween the results. Would the relations be the same using
> maximally optimized implementation?
>
> this is a table with speeds of encryption, decryption and average:
>
> Memory Speed Test for Cipher in Mode: cmECB
>
> Algorithm Encode Mb/sec Decode Mb/sec Ø Mb/sec
>
> 3Way 8,29 7,67 7,980
> Blowfish 19,47 19,71 19,594
> Gost 9,97 11,53 10,746
> IDEA 7,56 7,52 7,542
> Q128 17,59 35,23 26,410
> SAFER-K40 8,95 9,13 9,043
> SAFER-SK40 8,96 9,26 9,108
> SAFER-K64 7,13 7,29 7,213
> SAFER-SK64 7,57 7,42 7,498
> SAFER-K128 4,79 4,76 4,777
> SAFER-SK128 4,82 4,76 4,790
> SCOP 49,61 76,70 63,156
> Shark 11,98 10,31 11,141
> Square 21,46 22,53 21,995
> TEA 16,29 18,18 17,239
> TEA extended 15,11 17,89 16,500
> Twofish 15,29 18,08 16,683
> Sample Cipher 32,10 46,01 39,058
> Cast 128 16,26 21,21 18,737
> Cast 256 10,96 11,95 11,453
> DES Single 8byte 9,28 10,14 9,712
> DES Double 8byte 3,45 3,55 3,502
> DES Double 16byte 3,55 3,61 3,581
> DES Triple 8byte 3,54 3,56 3,553
> DES Triple 16byte 3,51 3,61 3,562
> DES Triple 24byte 3,46 3,55 3,504
> DESX 9,04 9,98 9,510
> Diamond II 4,26 4,29 4,272
> Diamond II Lite 3,83 4,02 3,926
> FROG 5,52 7,60 6,563
> Mars 12,00 12,47 12,231
> Misty 1 6,15 6,62 6,386
> NewDES 6,15 6,10 6,124
> RC2 4,11 3,58 3,843
> RC4 22,43 25,62 24,027
> RC5 21,30 25,61 23,455
> RC6 13,87 15,23 14,548
> Rijndael 17,46 17,42 17,437
> Sapphire II 13,46 14,52 13,990
> Skipjack 4,99 5,22 5,105
>
> I would appreciate very much your help. (I need this comparison for my
> assignment, it's quite important for me)
> Maciek
>
>
------------------------------
From: "Matt Timmermans" <[EMAIL PROTECTED]>
Subject: Re: Quick CRT question:
Date: Thu, 28 Dec 2000 21:33:31 GMT
"Bryan Olson" <[EMAIL PROTECTED]> wrote in message
news:92g460$pj5$[EMAIL PROTECTED]...
> Matt Timmermans wrote:
>
> [...]
> > 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))
>
> That sum can be larger than Q (even if we add the requirement
> on a_i that 0 <= a_i < q_i), so we need mod Q at the end. It
> still runs in O(n^2).
Benjamin's OP said that we are using polynomials over GF(2), which don't
have this problem. degree(a_i)<degree(q_i), so degree(a_i*Q_i)<degree(Q).
------------------------------
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: [EMAIL PROTECTED] (nobody)
Subject: Re: "Content Protection for Recordable Media"
Date: Thu, 28 Dec 2000 22:29:24 GMT
>Dumb quesion: What prevents one from reading from such a
>drive into memory and writing out to a drive without
>protection features, which some manufacturers of the world
>would certainly continue to produce to meet a corresponding
>market demand?
the info is stored on the drive in encrypted form. you can copy the
encrypted files as any other ordinary files. e.g. to a non-compliant
drive.
to decrypt, you will need to obtain a licence to get the requisite
info.
--
pel
------------------------------
From: Simon Johnson <[EMAIL PROTECTED]>
Subject: Re: Random keys of arbitrary length
Date: Thu, 28 Dec 2000 22:31:06 GMT
> So here's what I've been doing. Basically, I use the hash of a
passphrase
> to key a stream cipher, and then use the stream cipher's keystream to
create
> keys and IVs:
>
> 1. Have the user enter a passphrase. Make sure it's at least twenty
> characters long.
> 2. Run the passphrase through both SHA1 and MD5 (separately), giving
> two hashes.
MD5 has a theortical weakness but i don't think it can be exploited.
There is really no need to run the passphrase through two hashing
algorithms. One run with SHA-1 is enough, and its faster.
> 3. Concatenate the hashes, giving a 288-bit value, and initialize RC4
> with that.
This is fine, but RC4 takes 2048-bit keys, and with your method only a
288-bit key is supplied. This isn't really a problem, but it appears to
me that you used two different hashes so you could increase the amount
of bits you have to initialise.
Its is stupidly unlikely that a 288-bit key could never be broken by
brute-force. However, you say the minimal excepted length for your
passphrase is 20 characters. Well a 20 character pass-phrase contains
only 160-bits, again this isn't a real problem 160-bits will not be
breakable for the foreseeable future.
> 4. Whenever a random byte is needed, have RC4 return a byte
> of "keystream"
> and use that.
>
> How secure do you think that is? Is it a good or bad idea to create
> IVs from the same source as the keys?
It depends on the security of the PRNG, and how the generated key will
be used.
The security of the system depends apon its weakest algorithm. MD5 and
SHA-1 are good algorithms, RC4 is Ok. If your a real security freak
insure that you use a BBS-PRNG instead of RC4. A BBS is slower but
provably secure. Speed really isn't an issue for key-generation.
Simon.
--
Hi, i'm the signuture virus,
help me spread by copying me into Signiture File
Sent via Deja.com
http://www.deja.com/
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: "Content Protection for Recordable Media"
Date: Thu, 28 Dec 2000 22:54:38 GMT
On Thu, 28 Dec 2000 20:23:07 +0100, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote, in part:
>Dumb quesion: What prevents one from reading from such a
>drive into memory and writing out to a drive without
>protection features, which some manufacturers of the world
>would certainly continue to produce to meet a corresponding
>market demand?
What happens is this:
Normally, files are written to, and read from, the drive like any
other drive, and they can be copied.
But content-protected files, when written to the drive, are in
encrypted form. And the key to the encryption is written on a part of
the hard drive which is not directly accessible.
The program writing the file to the hard drive specifies something
like a password, and the viewer program which is the only thing
allowed to read the file knows this password. Since the password needs
to be combined with the key on that particular drive to decrypt the
file, it can only be turned into its unencrypted form by the viewer
programs that know the right password, and on the specific machine on
which it was installed.
Thus, copying it in encrypted form is useless. And if you don't have
one of those new-style drives, you won't be able to download the
content which is only for distribution to them.
This does create a problem of backup, since what if one wants to take
this kind of content temporarily off of that hard drive to use the
space for something else? It is assumed that it is good enough to
allow individual content providers to each have their own scheme for
transferring protected content from one user's hard drive somewhere
else.
I think that a general backup feature could have been provided without
compromising the scheme's security; simply give each of these hard
drives a serial number, and a unique, secret, encryption key, and
allow encrypted files to be exported with the key, as encrypted by the
drive's unique key. That way, one can back up the entire hard drive in
a normal way, even if it contains a large quantity of content of this
type from many different providers.
A means of exchanging disk IDs between disks would facilitate
upgrading one's hard drive as well. That does allow content to be
moved, but not duplicated, and again, the alternative would be to make
it so cumbersome to have content from multiple providers that this
scheme would not be attractive. (If individual content providers can
supply programs that copy the file to another machine after verifying
the original copy is erased, why not include the equivalent program
for disk IDs, thereby creating confidence that backups and upgrades
will be possible, and that they can be done in a single step, not in
hundreds of steps?)
These two features, then, a disk ID and a means of exchanging it, are
what is missing to allow the security feature to be acceptable for
broader use.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
