Cryptography-Digest Digest #273, Volume #12 Sun, 23 Jul 00 13:13:00 EDT
Contents:
Re: Guardian 19/7/2000: "That charter for snoopers" (Andy Mabbett)
Re: Random Appearance (Future Beacon)
Re: Question Regarding Encrypting CD-ROM -RW Disks (jungle)
Re: Crypto jokes? (potentially OT) (Sundial Services)
Re: Question Regarding Encrypting CD-ROM -RW Disks (Sundial Services)
Proving continued possession of a file (Mark Wooding)
Re: 8 bit block ciphers ("Douglas A. Gwyn")
Re: Proving continued possession of a file (Nicol So)
Re: Proving continued possession of a file (Edward Keyes)
Re: 8 bit block ciphers (Boris Kazak)
Re: Proving continued possession of a file ("Scott Fluhrer")
Re: Proving continued possession of a file (Boris Kazak)
Re: Proving continued possession of a file (Mack)
Re: 8 bit block ciphers (Mack)
Re: 8 bit block ciphers (Mack)
----------------------------------------------------------------------------
From: Andy Mabbett <[EMAIL PROTECTED]>
Crossposted-To:
uk.media.newspapers,uk.legal,alt.security.pgp,alt.privacy,uk.politics.parliament,uk.politics.crime,talk.politics.crypto,alt.ph.uk,alt.conspiracy.spy,alt.security.scramdisk,uk.telecom,uk.finance,uk.local.east-anglia,alt.politics.british
Subject: Re: Guardian 19/7/2000: "That charter for snoopers"
Date: Sun, 23 Jul 2000 10:57:37 +0100
In article <[EMAIL PROTECTED]>, Cyril
Disobedient <[EMAIL PROTECTED]> writes
>Special report: free speech on the net
uk.media.newspapers us for discussion /of/ newspapers in the UK; not
merely the reposting of articles. Please desist.
(FU set)
--
Andy Mabbett
"I've been meaning to tidy up, but you know how it is:
you blink and - whoops - another year gone"
------------------------------
From: Future Beacon <[EMAIL PROTECTED]>
Subject: Re: Random Appearance
Date: Sun, 23 Jul 2000 08:40:25 -0400
On Sun, 23 Jul 2000, Douglas A. Gwyn wrote:
> Future Beacon wrote:
> > I am convinced that it is possible.
>
> Basic information theory says otherwise.
>
> For your notion to work, the input plaintext would have to
> be restricted to a selection from a limited set, not a
> completely general message of length N.
>
Do you have a proof?
Jim Trek
Future Beacon Technology
http://eznet.net/~progress
[EMAIL PROTECTED]
------------------------------
From: jungle <[EMAIL PROTECTED]>
Subject: Re: Question Regarding Encrypting CD-ROM -RW Disks
Date: Sun, 23 Jul 2000 08:54:36 -0400
yes, the AGENCIES have the way to do it ...
they have the way to ELIMINATE anyone from the surface to ...
but the fact is :
the hammer will not destroy data but ONLY drive ...
&
the sensitivity level of data on H/D is irrelevant ...
Sundial Services wrote:
>
> :-) If the information on your hard-drive is that sensitive, that
> someone would work that damned hard to recover it, then "they'll find a
> way to put you in jail anyway." ;-)
>
> >jungle wrote:
> >
> > Greg wrote:
> > ==========
> > > The point
> >
> > your point will not protect your data "in a hurry" against AGENCIES work ...
> >
> > > I am making is that with my notebook, and others like it
> > > I am sure, if you had to destroy the HD in a hurry, you could simply
> > > slide it out and go at it with a sledge hammer.
> >
> > hammer is not destroying data but ONLY DRIVE ...
> > you need to understand the difference ...
> >
> > > These drives are
> > > tiny, thin, and very susceptible to any pressure on their top surface.
> >
> > what above has to do with destroying magnetic data ?
> > ANSWER : almost nothing ...
------------------------------
Date: Sun, 23 Jul 2000 06:30:52 -0700
From: Sundial Services <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Crypto jokes? (potentially OT)
I've always had the unpleasant feeling that the real reasoning on this
was, "we don't want to have to share the patents with the school down
the street." (Gotta share it with the student but we can bully him out
of "our half of it." He's starving, you know.)
>Douglas A. Gwyn wrote:
> [...]
> The idea that when an idea is independently discovered by
> multiple researchers, the first one to reach print gets all
> the credit has always been screwy. It leads to such things
> as a graduate student having to start his thesis work all
> over because his independent work is no longer considered
> "original research" and thus does not qualify for a degree.
> So long as everybody is convinced that the researchers did
> work independently and were not aware of each other's work,
> in a rational world they should share credit for the invention.
> The main question is whether the earlier work was partially
> "leaked" and the later work was inspired by that information,
> in which case only the earlier work is the true innovation.
------------------------------
Date: Sun, 23 Jul 2000 06:32:56 -0700
From: Sundial Services <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Question Regarding Encrypting CD-ROM -RW Disks
Come to think of it, the way I'd destroy a CD-R or CD-RW disk is with a
buffing wheel or polishing wheel. If the NSA can reconstruct the data
in that little pile of green plastic dust on the floor of the workshop,
they can be my guest. So to speak.
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Proving continued possession of a file
Date: 23 Jul 2000 13:46:19 GMT
A while ago, I was asked to come up with some mechanism whereby a server
could ascertain whether a client, which had previously transferred a
particular file to the server, still had a copy of that file itself. I
finally came up with something plausible (yet utterly impractical)
yesterday evening, and I thought I'd share it with the group.
Let's call the file's data M, and we'll suppose that Alice is running
the server, and Bob is running the client. Last week, Alice knows that
Bob had the file M, and he sent it to her. This week, Bob claims to
still have the file, but Alice isn't convinced.
To run this protocol, Alice thought up two primes, p and q, which form
her private key, and sent Bob n = p q as a public value. When Bob sent
her M last week, she computed
M_p = M mod (p - 1); M_q = M mod (q - 1)
and stored them away.
Now, Bob claims to still have the file. Alice thinks up a /challenge/
x, where 1 < x < n and x is relatively prime to n, and sends it to Bob.
She asks him to compute R = x^M (mod n). Bob complains that this will
take ages, but Alice says that she doesn't have a better way to work
this right now, and network bandwidth is more expensive than Bob's time,
so Bob gets his paper and pencil out and starts calculating. He
eventually sends Alice a number R'.
Alice then checks that
R' = (x mod p)^{M_p} (mod p); and
R' = (x mod q)^{M_q} (mod q) .
If both of these are true then she believes Bob; otherwise she gives him
an earful and refuses to play Mental Poker with him for a week.
Alice is basically computing x^{M mod \phi(n)} mod n in the verification
stage, although she breaks R' apart mod p and q rather than combining
her results using the Chinese Remainder Theorem, because it's slightly
faster that way.
The protocol works (if indeed it does) because Bob doesn't know the
order of x or any multiple of it, and therefore can't compute summary
information about M. In particular, the obvious summary information is
M mod \phi(n), but knowing \phi(n) would allow him to factor n. (We'll
assume that he can't do that.)
I've not finished thinking about evil ways in which Bob can /choose/ the
file M he wants to convince Alice that he still has, even though he
deleted it to make way for... oh, Bob doesn't want me to say what he
needed the disk space for.
Anyway, choosing M of a special form so that Bob doesn't have to
remember the whole thing is legitimate, /assuming/ that the information
he retains isn't sufficient to reconstruct M completely.
And finally, can anyone think of more sensible protocols which have
similar properties but save Bob from having to do all of that
computation?
-- [mdw]
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: 8 bit block ciphers
Date: Sun, 23 Jul 2000 11:09:03 -0400
Mack wrote:
> I am looking for something that could be implemented without
> having the entire table in memory. For example only using
> 32 bytes. This prevents shuffling from being useful.
> I am looking for something that will take a 32 byte key
> and convert it to an 8 bit permutation. The permutation
> should have a good non-linearity, good avalanche and
> a good differential table. It should also be invertable.
> Methods that use fewer key bytes are acceptable.
> Basically it has to be a good 8-bit encryption method.
Using less than 256 bytes of code?
Your "requirements" don't make sense.
------------------------------
From: Nicol So <[EMAIL PROTECTED]>
Subject: Re: Proving continued possession of a file
Date: Sun, 23 Jul 2000 12:03:49 -0400
Reply-To: see.signature
Mark Wooding wrote:
>
> A while ago, I was asked to come up with some mechanism whereby a server
> could ascertain whether a client, which had previously transferred a
> particular file to the server, still had a copy of that file itself. I
> finally came up with something plausible (yet utterly impractical)
> yesterday evening, and I thought I'd share it with the group.
>
> [solution omitted]
Have you overlooked a *much* simpler solution?
--
Nicol So, CISSP // paranoid 'at' engineer 'dot' com
Disclaimer: Views expressed here are casual comments and should
not be relied upon as the basis for decisions of consequence.
------------------------------
From: [EMAIL PROTECTED] (Edward Keyes)
Subject: Re: Proving continued possession of a file
Date: 23 Jul 2000 12:14:28 EDT
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Mark Wooding) wrote:
> A while ago, I was asked to come up with some mechanism whereby a server
> could ascertain whether a client, which had previously transferred a
> particular file to the server, still had a copy of that file itself. I
> finally came up with something plausible (yet utterly impractical)
> yesterday evening, and I thought I'd share it with the group.
[snip]
> And finally, can anyone think of more sensible protocols which have
> similar properties but save Bob from having to do all of that
> computation?
How about the server sends the client a small bit of random data
and asks the client to compute:
HASH(RANDOM+FILE)
This is easy for the client to do, easy for the server to verify,
and extremely unlikely to be able to fake if you don't still have
a copy of the file.
+------------ Edward Keyes, [EMAIL PROTECTED] -------------+
|................ http://web.mit.edu/eakeyes/www/ ................|
|.... DaggerWare: "small, sharp, and with a heck of a point!" ....|
+- "A little inaccuracy saves a world of explanation." C.E.Ayres -+
------------------------------
From: Boris Kazak <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: 8 bit block ciphers
Date: Sun, 23 Jul 2000 16:16:50 GMT
Mack wrote:
>
> I am looking for something that could be implemented without
> having the entire table in memory. For example only using
> 32 bytes. This prevents shuffling from being useful.
>
> I am looking for something that will take a 32 byte key
> and convert it to an 8 bit permutation. The permutation
> should have a good non-linearity, good avalanche and
> a good differential table. It should also be invertable.
> Methods that use fewer key bytes are acceptable.
> Basically it has to be a good 8-bit encryption method.
>
> Does anyone have something that fits the bill?
>
> Mack
> Remove njunk123 from name to reply by e-mail
=========================
Seems entirely possible.
You just arrange your 32 bytes in a kind of a shift register,
initialize it with the key, and arrange a system of taps in
order to modify the content of the register while shifting.
Then you shift it 8 positions, capture 8 bits and use them as
your encryption byte.
The positioning of taps and the operations that you perform on
the register data will determine the period of this generator.
Best wishes BNK
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Proving continued possession of a file
Date: Sun, 23 Jul 2000 09:14:22 -0700
Mark Wooding <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> A while ago, I was asked to come up with some mechanism whereby a server
> could ascertain whether a client, which had previously transferred a
> particular file to the server, still had a copy of that file itself. I
> finally came up with something plausible (yet utterly impractical)
> yesterday evening, and I thought I'd share it with the group.
>
> Let's call the file's data M, and we'll suppose that Alice is running
> the server, and Bob is running the client. Last week, Alice knows that
> Bob had the file M, and he sent it to her. This week, Bob claims to
> still have the file, but Alice isn't convinced.
>
>
> To run this protocol, Alice thought up two primes, p and q, which form
> her private key, and sent Bob n = p q as a public value. When Bob sent
> her M last week, she computed
>
> M_p = M mod (p - 1); M_q = M mod (q - 1)
>
> and stored them away.
>
> Now, Bob claims to still have the file. Alice thinks up a /challenge/
> x, where 1 < x < n and x is relatively prime to n, and sends it to Bob.
> She asks him to compute R = x^M (mod n). Bob complains that this will
> take ages, but Alice says that she doesn't have a better way to work
> this right now, and network bandwidth is more expensive than Bob's time,
> so Bob gets his paper and pencil out and starts calculating. He
> eventually sends Alice a number R'.
>
> Alice then checks that
>
> R' = (x mod p)^{M_p} (mod p); and
> R' = (x mod q)^{M_q} (mod q) .
>
> If both of these are true then she believes Bob; otherwise she gives him
> an earful and refuses to play Mental Poker with him for a week.
>
>
> Alice is basically computing x^{M mod \phi(n)} mod n in the verification
> stage, although she breaks R' apart mod p and q rather than combining
> her results using the Chinese Remainder Theorem, because it's slightly
> faster that way.
>
> The protocol works (if indeed it does) because Bob doesn't know the
> order of x or any multiple of it, and therefore can't compute summary
> information about M. In particular, the obvious summary information is
> M mod \phi(n), but knowing \phi(n) would allow him to factor n. (We'll
> assume that he can't do that.)
>
> I've not finished thinking about evil ways in which Bob can /choose/ the
> file M he wants to convince Alice that he still has, even though he
> deleted it to make way for... oh, Bob doesn't want me to say what he
> needed the disk space for.
>
> Anyway, choosing M of a special form so that Bob doesn't have to
> remember the whole thing is legitimate, /assuming/ that the information
> he retains isn't sufficient to reconstruct M completely.
>
> And finally, can anyone think of more sensible protocols which have
> similar properties but save Bob from having to do all of that
> computation?
How about this: Alice picks several distinct 64 bit primes p_i, and sends
them to Bob. Bob takes the entire file as a bigendian integer M, and sends
back (M mod p_i).
Bob can, of course, store a summary of the file, rather than the actual
file. However, if Alice sends 8 primes p_i, and Bob wants a 1 in
2^{-32}chance of passing this test, he must have a 2^{-3}probability of
deriving each modulo, and since there are about 2^{58} 64 bit primes, that
appears to means that Bob must store sufficient information to retrieve
2^{55} 64 bit numbers, or 2^{58} bytes. Unless the file is extremely long,
this "summary" is longer than the file itself.
This, of course, works by using the CRT to show that, if you know a bounded
integer to a sufficient number of relatively prime modulii, you can
reconstruct the integer. And so, knowing a random subset of the modulii is
probabilistic proof of knowing the integer.
Oh, and if Bob chose x to be in a special form (say, all zeros), he can
easily compute the above, but you could also claim in that case, he still
had the file, just not in explicit form...
This does assume Alice has a copy of M still around, or knew in advance how
many times she would make this query. Your protocol doesn't assume that --
is that a problem? And, this has the disadvantage that someone listening in
to a sufficient number of these queries could reconstruct the file.
However, you didn't mention that as a problem, I just note it.
--
poncho
------------------------------
From: Boris Kazak <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Proving continued possession of a file
Date: Sun, 23 Jul 2000 16:33:21 GMT
Mark Wooding wrote:
>
> A while ago, I was asked to come up with some mechanism whereby a server
> could ascertain whether a client, which had previously transferred a
> particular file to the server, still had a copy of that file itself. I
> finally came up with something plausible (yet utterly impractical)
> yesterday evening, and I thought I'd share it with the group.
>
> Let's call the file's data M, and we'll suppose that Alice is running
> the server, and Bob is running the client. Last week, Alice knows that
> Bob had the file M, and he sent it to her. This week, Bob claims to
> still have the file, but Alice isn't convinced.
>
> *******************
> And finally, can anyone think of more sensible protocols which have
> similar properties but save Bob from having to do all of that
> computation?
>
> -- [mdw]
====================
How about a simple and straight forward usage of a hash function.
Alice sends Bob a 256-bit random nonce. She asks him to prepend
the nonce to the M file, compute the hash and send the hash back to her.
She does the same operation with the copy of file she received.
If the two hashes match... Bob is exonerated.
Keeping the hash of M from the old times will not help, because
there is no realistic way of calculating a new hash with prepended
nonce (not _appended_, for God's sake!).
Best wishes BNK
------------------------------
From: [EMAIL PROTECTED] (Mack)
Subject: Re: Proving continued possession of a file
Date: 23 Jul 2000 16:47:59 GMT
>
>And finally, can anyone think of more sensible protocols which have
>similar properties but save Bob from having to do all of that
>computation?
>
>-- [mdw]
>
A better way would be to use a hash function.
Put the verification data at the front and compute
the hash. Putting the verification data at the back
allows a partial hash to be computed and then
saving that infomation until needed.
This is a bit better than the method using prime fields.
M of special form is 'impossible' to find for a secure hash.
Another method is to use a selected password
to encrypt the file and then take the hash. There should be
no way to find the new hash without the password.
Both of these methods do what you describe.
Your method has the problem that bob just
needs to keep M mod n if n is constant.
If n really is as big as M this method is VERY slow for
really big files.
In either case alice either needs the file on the server
or bob must send her another copy to verify the
results.
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
From: [EMAIL PROTECTED] (Mack)
Subject: Re: 8 bit block ciphers
Date: 23 Jul 2000 16:57:14 GMT
>Mack wrote:
>> I am looking for something that could be implemented without
>> having the entire table in memory. For example only using
>> 32 bytes. This prevents shuffling from being useful.
>> I am looking for something that will take a 32 byte key
>> and convert it to an 8 bit permutation. The permutation
>> should have a good non-linearity, good avalanche and
>> a good differential table. It should also be invertable.
>> Methods that use fewer key bytes are acceptable.
>> Basically it has to be a good 8-bit encryption method.
>
>Using less than 256 bytes of code?
>Your "requirements" don't make sense.
>
Less than 256 bytes of RAM. Think embedded
applications.
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
From: [EMAIL PROTECTED] (Mack)
Subject: Re: 8 bit block ciphers
Date: 23 Jul 2000 17:02:09 GMT
>
>Mack wrote:
>>
>> I am looking for something that could be implemented without
>> having the entire table in memory. For example only using
>> 32 bytes. This prevents shuffling from being useful.
>>
>> I am looking for something that will take a 32 byte key
>> and convert it to an 8 bit permutation. The permutation
>> should have a good non-linearity, good avalanche and
>> a good differential table. It should also be invertable.
>> Methods that use fewer key bytes are acceptable.
>> Basically it has to be a good 8-bit encryption method.
>>
>> Does anyone have something that fits the bill?
>>
>> Mack
>> Remove njunk123 from name to reply by e-mail
>-------------------------
>Seems entirely possible.
>You just arrange your 32 bytes in a kind of a shift register,
>initialize it with the key, and arrange a system of taps in
>order to modify the content of the register while shifting.
>Then you shift it 8 positions, capture 8 bits and use them as
>your encryption byte.
>The positioning of taps and the operations that you perform on
>the register data will determine the period of this generator.
>
>Best wishes BNK
>
Good idea but is too linear. At least for provable
long generators. With a 32 byte shift register this will
duplicate bytes before the complete table. I am looking for
something that works like an 8-bit block cipher.
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
