Cryptography-Digest Digest #193, Volume #13 Mon, 20 Nov 00 19:13:01 EST
Contents:
Re: XOR: A Very useful and important utility to have (Antonio Varni)
Re: simple proof (Gregory G Rose)
Re: proof of equation (David Schwartz)
Re: vote buying... (Shawn Willden)
Re: Total $ spent on voice encryption (Mok-Kong Shen)
The Last On means 1st Off Rule ([EMAIL PROTECTED])
Re: hardware RNG's (Tim Tyler)
Re: [Question] Generation of random keys (John Myre)
Proof of posession (Matthew Skala)
Re: hardware RNG's (David Schwartz)
Re: The Last On means 1st Off Rule ("Scott Fluhrer")
Re: how can we show this ("Scott Fluhrer")
Re: The Last On means 1st Off Rule (Paul Rubin)
Re: equation problem ("Scott Fluhrer")
Re: Question regarding OS's. ("Juri")
----------------------------------------------------------------------------
From: Antonio Varni <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto,alt.hacker,alt.computer
Subject: Re: XOR: A Very useful and important utility to have
Date: Mon, 20 Nov 2000 14:24:34 -0800
Guy Macon wrote:
>
> Anthony Stephen Szopa wrote:
>
> >
> >XOR: A Very useful and important utility to have
> >
> >A few people in this news group said any XOR program is less than
> >useless.
> >
>
> Balderdash. What people have said is that *YOUR*
> XOR program is less than useless. Which it is.
>
> Why?
>
> [1] It's 156KB zipped. Bloatware Alert! Bloatware Alert!
Exactly. A program to do this XORing can be written in under 20 lines
in python or perl -- I've seen utilities that do this in C in about 200
lines. They are all open source.
>
> [2] You haven't published the source code. Security Risk! Security Risk!
>
> [3] You have a random number generator and an encryption system that
> you don't advertise, yet you push this little utitity. **A lot**...
>
> A reasonable persoin would suspect that you have something hidden in
> the code that you don't want users to know about. Which makes it
> less than useless.
------------------------------
From: [EMAIL PROTECTED] (Gregory G Rose)
Subject: Re: simple proof
Date: 20 Nov 2000 13:43:03 -0800
In article <8vbfs5$dqv$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
>Let's say that we have a function, such that
>
>f(n) = Sum{i =0, n-1} 2^i
>
>how can we show these two:
>one:
>f(n) = f(n-1) +2^(n-1)
>
>second:
>f(n) = 2f(n-1) +1
Write the equations on a piece of paper using
special electrically conductive ink. Make sure you
use cursive writing, as separate printed characters won't
work properly. Draw a thick closed line around the
equations.
Now mount a very large rotating magnet above the
piece of paper. A field of a couple of Tesla
should work. Make sure it rotates fast, say
2000RPM.
If you've done it right, the paper will burn up,
proving the results by induction.
Greg.
--
Greg Rose INTERNET: [EMAIL PROTECTED]
QUALCOMM Australia VOICE: +61-2-9181 4851 FAX: +61-2-9181 5470
Suite 410, Birkenhead Point http://people.qualcomm.com/ggr/
Drummoyne NSW 2047 B5 DF 66 95 89 68 1F C8 EF 29 FA 27 F2 2A 94 8F
------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: proof of equation
Date: Mon, 20 Nov 2000 13:42:49 -0800
> Sorry for a remark. There are recently quite a number
> of threads that clearly belong to sci.math and not
> to sci.crypt.
>
> M. K. Shen
And they all start at Deja.
DS
------------------------------
From: Shawn Willden <[EMAIL PROTECTED]>
Subject: Re: vote buying...
Date: Mon, 20 Nov 2000 14:57:08 -0700
Paul Rubin wrote:
> David Hopwood <[EMAIL PROTECTED]> writes:
> > All the attempted solutions I've seen fail to solve the problem that
> > voters' authentication credentials can be bought. (Authentication
> > credentials are whatever a voter knows or has that proves that they
> > are eligible to vote, and that distinguishes them from another voter -
> > e.g. keys or smartcards.)
>
> If we're talking about poll voting, they authenticate you at the polls
> (photo ID etc). If we're talking about voting over the internet,
> that's a bad idea because it sacrifices non-coercability (the
> receipt-free property) by letting you vote with someone else watching.
> Even if there is some kind of foolproof biometric authentication
> device that you can plug into your computer when you vote, you can
> still sell your vote by just letting the buyer see how you vote.
It's interesting to note that the voting schemes we currently use fail this
test as well. If I want to buy your vote, I just have you request an
absentee ballot which I fill out for you and mail in. Maybe this isn't an
important test.
Shawn.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Total $ spent on voice encryption
Date: Mon, 20 Nov 2000 23:06:03 +0100
[EMAIL PROTECTED] wrote:
>
> Why do business spent Billions $ for all kinds of data security but will not
> spend money on voice encryption as if wiretapping and eavesdropping is not
> happening.
Probably I haven't understood your question, but there
are voice encryption devices (one mentioned by someone
previously in the group is based on DES) employed by
the business people. Or do you mean that the security
provided isn't sufficient in your view?
M. K. Shen
------------------------------
From: [EMAIL PROTECTED]
Subject: The Last On means 1st Off Rule
Date: Mon, 20 Nov 2000 22:22:36 GMT
Simon Singh has said that no strong ciphers exist
(or existed in the 70's) which work without the
above rule. In other words a text encrypted with
key/process A and then with B would needed to be
decrypted with B first. By accident I have found
and improved a cipher which does not insist on
this, so it could be used between correspondents
without their need to share keys at all
(see 'CodeBook' by Simon Singh, circa p259). For
a 1Kb message I beleive 1E20 pentium*years would
be needed - at least. If a 'linear' cracking
process cannot be found then computer
requirements for longer messages go up
exponentially.
The idea is to pre-process the text without use
of a key to scramble into one-character word
fragments and then convert to HEX. Load into a
2D array (with odd number of columns and rows -
filling undef. with junk) and have a decimal PRNG
move the columns down by 0 to 9 places, returning
hex characters to the top of the column.
Rotations are accumulative and can be added or
removed in ant order. Please comment on how
often this has been noted before, how useful and
what are the main problems - does anyone want a
challenge?
Tony Marsh
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: hardware RNG's
Reply-To: [EMAIL PROTECTED]
Date: Mon, 20 Nov 2000 22:50:07 GMT
David Schwartz <[EMAIL PROTECTED]> wrote:
: Tim Tyler wrote:
:> David Schwartz <[EMAIL PROTECTED]> wrote:
:> [defining terms]
:>
:> : I use "random" (in a cryptographic context) to mean unpredictable (by
:> : an attacker with a specific presumed set of resources). How random
:> : something is is the same question as to what extent a hypothetical
:> : attacker could predict it.
:>
:> How does that square with your supposedly-random dice with a '1' on one
:> side and a '2' on five other sides?
:>
:> Surely the attacker would predict that it would come up with a "2" showing
:> - and be right much of the time?
: Exactly. But we know exactly how often he'd be right and exactly how
: often he'd be wrong. So we have some randomness, and we know how much.
: So this randomness is cryptographically usable.
I think we've now strayed from the question of whether something
which typically looks something like:
"10000000001010000000010000010001000000000000010001000011000000" can
be called a random stream. Certainly such a stream can contain some
randomness - but IIRC that was not the issue at hand.
: The important thing is that you have a reliable lower bound on how much
: randomness you have.
With a six sided dice? Are the numbers drilled out? Painted on?
How high is the dice lifted from the table between rolls? Could
an attacker listen to the sound of the dice rolling somehow?
Or surreptitiously replace the dice with one of his own manufacture?
That a reliable lower bound can be easily established is far-from obvious.
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: [Question] Generation of random keys
Date: Mon, 20 Nov 2000 15:52:30 -0700
[EMAIL PROTECTED] wrote:
<snip>
> Actually very hard. The first problem is finding a balanced coin. What
> I would suggest instead is taking the coin, flipping it 100 time, use
> that as entropy, and to compute the approximate bias in the coin.
<snip>
This is truly bizarre. Do you actually think that a bias estimate
derived from 100 flips is meaningful when attempting to obtain
160 bits of entropy?
Take a random coin out of your pocket, a different one each time
you want to generate 160 bits, and the result will be fine, in
any practical sense. In a theoretical sense (the one you seem
to care about), you would need a *lot* more than 100 flips to
create the certainty about the bias that you would need, to "know"
when you had 160 bits of entropy (and not, say 158). Otherwise,
how could you *ever* create, say, the all zero key?
JM
------------------------------
From: [EMAIL PROTECTED] (Matthew Skala)
Subject: Proof of posession
Date: 20 Nov 2000 15:09:32 -0800
Cheating in peer-to-peer file sharing systems is currently a fairly minor
problem, but I expect it will become worse. The general problem is that
files available through the system are not always as advertised. A user
may download a file and then discover that it's much lower quality than
expected, is missing part of the content, or includes or consists of an
advertisement for some product or ideology instead of whatever it was
supposed to be. I'll use the term "correct" to refer to a file that
really is whatever the downloading party expected it to be.
We could make a start on solving the problem by having some trusted party
(which need not be centralized, web-of-trust is fine) distribute a
cryptographic signature for each file. Since the signatures are probably
a lot smaller than the files, users could afford to download a database of
signatures and then check files against them to verify that the files are
correct. But that delays the check until after the download, which
isn't ideal. Ideally, someone who advertises a file would have some way
of proving that they have the file, before it's transmitted, and someone
who receives a file would be able to verify that it is the correct file,
during or before the download.
Well, verifying that a file is correct can't really be done until after
it's all downloaded. We could improve things a little bit by having the
authority sign chunks of the file, and then the receiver can verify each
one as soon as it's downloaded before bothering to download the rest.
But that's limited by how big we're willing to make the signatures, an
attacker could cause a whole lot of annoyance by giving out all the
chunks except the last one, and it sure looks like it's the best we can do.
What about proof of posession? If the person advertising the file can at
least prove that they *have* the correct file, then even though they might
not really transmit that file when someone tries to download it, it at
least forces them to maintain a copy of the correct file, and that will
filter out a lot of cheaters. It would seem that what we need here is
some kind of signature or proof-of-identity scheme where the correct file
is an indispensible part of the secret key and the public key is short
enough that users can conveniently store thousands of them.
The simplest thing we could do would be to just hash the file, use the
result as a seed for a random number generator, and then use that to
generate a public/private key pair for some standard scheme. That way,
the person advertising the file can prove posession of the private key,
and that shows that they had the cooperation of someone who had the file
at some point in the past, in order to generate the key. Unfortunately,
it doesn't put a big burden on the attacker because they don't need to
store the correct file - only its hash.
Is there a way to prove posession of a *large* secret, with a *small*
public key? I'm guessing that there may be a simple information theoretic
proof that this is impossible, but I'd be interested to hear anyone else's
thoughts on it.
--
Matthew Skala
[EMAIL PROTECTED] :CVECAT DELENDA EST
http://www.islandnet.com/~mskala/
------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: hardware RNG's
Date: Mon, 20 Nov 2000 15:17:02 -0800
Tim Tyler wrote:
> : Exactly. But we know exactly how often he'd be right and exactly how
> : often he'd be wrong. So we have some randomness, and we know how much.
> : So this randomness is cryptographically usable.
> I think we've now strayed from the question of whether something
> which typically looks something like:
> "10000000001010000000010000010001000000000000010001000011000000" can
> be called a random stream. Certainly such a stream can contain some
> randomness - but IIRC that was not the issue at hand.
To determine whether such a stream is "random" or not is the same as
determining whether it's unpredictable or not. And to do that, we have
to pose a hypothetical predictor with specific capability and determine
to what extent that predictor could succeed. The question requires we
suppose some specific set of abilities on behalf of the predictor. This
is why we seldom actually encounter the question "is X random". What we
actually encounter is something more like "is X suitable for purpose Y".
> : The important thing is that you have a reliable lower bound on how much
> : randomness you have.
> With a six sided dice? Are the numbers drilled out? Painted on?
> How high is the dice lifted from the table between rolls? Could
> an attacker listen to the sound of the dice rolling somehow?
> Or surreptitiously replace the dice with one of his own manufacture?
> That a reliable lower bound can be easily established is far-from obvious.
Remember that we are dealing with a supposed predictor with specific
supposed capabilities. If we were playing craps, we should suppose an
attacker who could hear the dice rolling or surreptitously replace the
dice (or take precautions against die replacement and then argue over
whether they're sufficient for us to ignore that possibility). As that
example shows, It may not always be very clear what capabilities we
should suppose, and this is legitimate grounds for argument when
deciding whether a particular randomness scheme is adequate for its
intended purpose.
DS
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: The Last On means 1st Off Rule
Date: Mon, 20 Nov 2000 15:21:23 -0800
<[EMAIL PROTECTED]> wrote in message news:8vc873$4dv$[EMAIL PROTECTED]...
> Simon Singh has said that no strong ciphers exist
> (or existed in the 70's) which work without the
> above rule. In other words a text encrypted with
> key/process A and then with B would needed to be
> decrypted with B first.
For a strong cipher with this property, look at the Polig-Hellman cipher.
It works like this:
C = (P**e) mod p
where:
P is the plaintext (between 0 and p-1)
C is the ciphertext
e is the secret key
p is a publicly known prime.
This is distinct from RSA in that the key must be secret. If A and B both
use it with the same p, when uses of it commute.
And, unless Mr. Singh specifically said that no strong ciphers known before
the '70s had this property, this does not say very much about his knowledge
as a cryptographer -- he really should have known about this.
> By accident I have found
> and improved a cipher which does not insist on
> this, so it could be used between correspondents
> without their need to share keys at all
> (see 'CodeBook' by Simon Singh, circa p259). For
> a 1Kb message I beleive 1E20 pentium*years would
> be needed - at least. If a 'linear' cracking
> process cannot be found then computer
> requirements for longer messages go up
> exponentially.
> The idea is to pre-process the text without use
> of a key to scramble into one-character word
> fragments and then convert to HEX. Load into a
> 2D array (with odd number of columns and rows -
> filling undef. with junk) and have a decimal PRNG
> move the columns down by 0 to 9 places, returning
> hex characters to the top of the column.
> Rotations are accumulative and can be added or
> removed in ant order. Please comment on how
> often this has been noted before, how useful and
> what are the main problems - does anyone want a
> challenge?
It's not particularly clear what your proposed algorithm is. Could you
please answer:
- Could you write up some pseudocode (or better yet, some compilable C or
Java) to demonstrate your cipher.
- It appears that all your cipher does is mix in some random data, and
permute the bits in some key dependant way -- at the least, I cannot see a
reference to any other operation. That is not particularly strong -- if the
message is N bits, then the attacker can deduce most of the permutation with
O(log(N)) known plaintexts.
--
poncho
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: how can we show this
Date: Mon, 20 Nov 2000 15:26:23 -0800
<[EMAIL PROTECTED]> wrote in message
news:8vbnk5$l05$[EMAIL PROTECTED]...
> How can we show that
>
> f(n) = n lg n for n even
> = n^1.5 for n odd
>
> ==> f = O(n^2)
>
>
> Suggestions please
This sounds an awful lot like homework, so I'll just give hints.
The notation:
f(x) = O( g(x) )
is defined to mean that there exist constants C, M such that
f(x) <= C * g(x) for all x > M
Suggestion: find such constants C, M
--
poncho
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: The Last On means 1st Off Rule
Date: 20 Nov 2000 15:31:17 -0800
[EMAIL PROTECTED] writes:
> Simon Singh has said that no strong ciphers exist
> (or existed in the 70's) which work without the
> above rule. In other words a text encrypted with
> key/process A and then with B would needed to be
> decrypted with B first.
This is incorrect--see any discussion of Shamir's three-pass protocol.
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: equation problem
Date: Mon, 20 Nov 2000 15:35:51 -0800
<[EMAIL PROTECTED]> wrote in message news:8vbkvf$iik$[EMAIL PROTECTED]...
> WE HAVE TO SHOW THAT
>
> (n^2)f(n) = ((n^2)-1)f(n-1)+2(n-1) => f(n) = 2((n+1)/n)*Hn - 4
>
>
> here Hn is not H muliply by n. instead it's the base n (very small n at
> the corner of H, I am not sure exactly how to express it)
>
> any suggestions
Sure:
- Why don't you look up what Hn means. It'd be real difficult to show this
without knowing what it means
- As written, the LHS does not imply the RHS. Why don't you go back and
find out what part of the problem you missed (ask the professor if
necessary)
- Once you have the missing piece, look up "proof by induction"
--
poncho
------------------------------
From: "Juri" <[EMAIL PROTECTED]>
Subject: Re: Question regarding OS's.
Date: Mon, 20 Nov 2000 23:53:47 GMT
Thanks very much for telling me...
I always wanted to try out unix...since I am
running nt4 right now. I have used linux a
little bit and I like what I am seeing.
Juri
Juri <[EMAIL PROTECTED]> wrote in message
news:x92S5.660712$[EMAIL PROTECTED]...
> Hello,
> I am just curious, why OS do you, cryptographers, use?
> Windows, Linux, Unix or something else?
> If Unix, what distributor of Unix? Thanks very much.
> Juri
>
>
------------------------------
** 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
******************************
