Cryptography-Digest Digest #334, Volume #13 Fri, 15 Dec 00 05:13:00 EST
Contents:
Re: Array shuffling ("Scott Fluhrer")
Re: breaking rsa knowing the original text ("Scott Fluhrer")
Re: Protocol for computer go (Francois Grieu)
Re: Protocol for computer go (Francois Grieu)
Re: ethical considerations ... (wtshaw)
Re: Fips Pub 140-1 and RNG ("Andrew Vincze")
Re: Crypto Program for HP48GX Calculator ([EMAIL PROTECTED])
Re: Crypto Program for HP48GX Calculator ([EMAIL PROTECTED])
Re: Crypto Program for HP48GX Calculator (Paul Rubin)
Re: Protocol for computer go (David Wagner)
Re: Protocol for computer go (David Wagner)
DUKPT using Triple DES (Mark Currie)
Re: Unguessable sequence of unique integers? ("Brian Gladman")
Re: security by obscurity ... (Anders Thulin)
Possibly Another Encryption Method - Any Thoughts ? (Kirk Whelan)
----------------------------------------------------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Array shuffling
Date: Thu, 14 Dec 2000 23:04:42 -0800
Benjamin Goldberg <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Scott Fluhrer wrote:
> >
> > Benjamin Goldberg <[EMAIL PROTECTED]> wrote in message
> > news:[EMAIL PROTECTED]...
> > - This algorithm looks like a randomized quicksort (minus the pivot
> > element), while the classical algorithm can be viewed as a randomized
> > selection sort (with optimizations).
>
> This algorithm is actually a randomized two bucket radix sort. Perhaps
> it looks a bit like quicksort, because of how I use buf to make two
> buckets (left bucket and right bucket), but it's not intended to
> resemble quicksort.
>
> > - This does appear to be unbiased, in the sense that it produces all
> > permutations with probability 1/N!, if all randbit() outputs are
> > unbiased and independent. I think I see an outline of a proof -- have
> > you proved it yourself?
>
> I've proved to myself (by construction, doing a diagram with pen and
> paper) that with N=3, the shuffle is unbiased, but I have not
> constructed a rigorous proof.
Actually, by showing that it is equivilant to a radix-two bucket sort of
random real numbers, a proof of even distribution is pretty trivial.
>
> > - Are you sure that your algorithm uses fewer expected random bits
> > than the classical algorithm? At N=3, the classical algorithm uses an
> > expected 3 2/3 random bits, while your algorithm uses an expected 5
> > bits. For N=4, the expected number of random bits are 5 2/3 for
> > classical, and 8 2/7 for yours.
>
> I am pretty certain that my algorithm uses an average of N*log(N) bits,
> simply because that is the number of tests radix sort needs to sort an
> array size N using 2 buckets. It should be trivial to convert a proof
> of the time complexity of radix sort into a proof of the complexity of
> this algorithm.
>
> For N=3, this means 4.7549 bits; for N=4, this means 8 bits. What do
> you mean "3 2/3", "5 2/3" and "8 2/7"? Three-and-a-third,
Actually, three and two thirds...
> five-and-two-thirds, eight-and-two-sevenths?
Yes. I computed the exact probabilities as exact fractions.
> Assuming that's what you mean, how do you calculate that the classical
> algorithm (the one with the swapping) uses 3.6667 bits to sort 3 items?
Well, the first thing it does is make a random selection of 3 items. The
obvious way to do that (which also happens to be optimal) is to generate 2
random bits, and if you get two ones, throw them both away and try again.
Each attempt uses 2 random bits, and you'll make an expected (1 + 1/4 + 1/16
+ 1/64 + ...) = 4/3 iterations, and so this uses an expected 2*4/3 = 2 2/3
random bits. Then (after doing the swap) it makes a random selection of the
remaining two items, and that takes a single random bit. Total: 3 2/3
random bits.
>
> The "optimal" algorithm, one which simply selects one of N! items,
> should take 2.5850 bits on average for N=3.
Errr, no. Converting random bits into a selection of N items consumes
strictly more than log2(N) random bits expected, unless N is a power of 2.
One way of looking at it is that there's no way to consume precisely 2.5850
bits, each application must consume 2 or 3 (or more) of bits, and the fact
that resolutions reside on multiple (in fact, an infinite number -- any
unbiased selection method must be potentially unbounded) of levels in the
decision tree degrade the efficiency somewhat.
>
> > In addition, as I referenced earlier, a maximally efficient modran
> > function (which can be efficiently computed) can make an unbiased
> > selection of N items using an expected log2(N)+O(1) random bits --
> > have you looked at the classical algorithm using that?
>
> Not yet... where do I find it? And you seem to have left out a "!"
> after N (in log2(N)+O(1)).
No, I got it right. I was talking about selecting between N items, not N!
permutations.
--
poncho
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: breaking rsa knowing the original text
Date: Thu, 14 Dec 2000 23:12:11 -0800
Jakob Jonsson <[EMAIL PROTECTED]> wrote in message
news:912aq0$d5g$[EMAIL PROTECTED]...
> "Bryan Olson" <[EMAIL PROTECTED]> skrev i meddelandet
> news:90p4r0$8d4$[EMAIL PROTECTED]...
> > [EMAIL PROTECTED] wrote:
> >
> > > Hi, I'm trying to figure out if it is much simpler to
> > > break RSA knowing the original text and the encrypted text.
> > > I mean, if some knows the original and the encrypted data
> > > how easy will be to get the key ??
> >
> > Giving an attacker ciphertext with corresponding
> > plaintext will not help him recover the RSA key. It's
> > a public key cipher so he can create all the plaintext/
> > ciphertext pairs he wants.
>
> He can create *as many* plaintext/ciphertext pairs as he wants but not
*all*
> plaintext/ciphertext pairs he wants. Namely, he may want to know the
> decryption of a particular ciphertext C -- this requires that he actually
> knows how to decrypt it or that he is able to ask someone to decrypt it
for
> him.
>
> This subtle difference is important; there was a chosen-ciphertext attack
> against the public-key algorithm NTRU at the CRYPTO 2000 conference
> (Jaulmes/Joux): If the adversary is able to ask an "oracle" for the
> decryption of ciphertexts chosen by himself, then he can find the key with
a
> high probability (given that he chooses the ciphertexts in a clever way).
> Without the oracle, the task of finding the key would be much harder for
the
> adversary.
Actually, a key recovery attack (that is, one that rederives the decryption
exponent) for RSA, given a decryption oracle, would be extremely
interesting. Since knowledge of both the encryption exponent and the
decryption exponent allows one to factor the modulus, this would imply that
solving the RSA problem is as difficult as factoring the modulus.
Currently, this is not known.
Of course, there are other reasons that padding before RSA is an extremely
good idea...
--
poncho
------------------------------
From: Francois Grieu <[EMAIL PROTECTED]>
Subject: Re: Protocol for computer go
Date: Fri, 15 Dec 2000 08:43:40 +0100
Paul Rubin <[EMAIL PROTECTED]> wrote:
> I have to say I've lost track of the proposal but I think the basic
> problem is this: Go-master Greg loses a game against the computer...
My problem was between two computers, but the it is basically the
same. Just one important point: we are willing to accept two things
which are very close to make the problem solvable:
- the programmer accepts to give the referee (essentialy in advance)
a special replay program specifically designed for replay of games,
working on a machine controlled by the referee.
- the programmer is willing to modify it's algorithms slightly for
this replay program to work, including making its code somewhat
deterministic.
With the above, the problem IS solvable, except for one "little"
detail: some (not all) programs needs to know how much of their
clock time has been used, and this same information must be
available to the replay program, else they can't produce the
same result. This is the only problem not solved yet.
Francois Grieu
------------------------------
From: Francois Grieu <[EMAIL PROTECTED]>
Subject: Re: Protocol for computer go
Date: Fri, 15 Dec 2000 08:50:02 +0100
[EMAIL PROTECTED] (David Wagner) wrote:
> Francois Grieu wrote:
> >Take of a program which plays one of two advise given by 2 process,
> >alledgedly depending on which took the less time. If a human, instead
> >of speed, decides the best move among the two [...]
>
> Yes. As I said, this is not secure in the sense that cryptographers
> are used to. But, for the purposes of ruling out cheating in Big Blue,
> I think this countermeasure is sufficient -- IBM is not going to buy
> a double-sized supercomputer just to be able to cheat in this way!
> Then again, we could argue whether any countermeasure is truly needed.
While I doubt IBM as a company would cheat, the guy that wrote the
program could. And it does NOT cost more hardware at all for the play
program: most programs will evaluate quite a few moves, and rank them,
thus can display the two best ones (according to their estimate) at
no cost. The hardware for the replay program cost nothing, as it is
to be supplied by the referee (else how would the referee know there is
no side channel, like a hidden memory with the moves played by the
real program, or a spread-spectrum RF receiver ?)
Francois Grieu
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: ethical considerations ...
Date: Fri, 15 Dec 2000 01:23:31 -0600
In article <[EMAIL PROTECTED]>, Paul Rubin
<[EMAIL PROTECTED]> wrote:
> "Peter Thorsteinson" <[EMAIL PROTECTED]> writes:
> > Do there exist any ethical considerations regarding the maintenance of a
> > secret? What if such maintenance could potentially do harm to others?
> >
> > Do there exist any ethical considerations regarding an attack on a secret?
> > What if the breach of the secret could potentially do harm to others?
>
> Of course there are, but this has nothing to do with cryptography.
Surely the general discussion does, or certain aspects of the field would
cause no problem. While people would like to separate out scientific
methods that contradict political expediency, meddlers on high fail to
respect methods or goals of scientific inquiry, which could also be used
to fairly count ballots, as some wish to protect us from the truth in as
many ways as they can.
--
No one should call themselves moral, certainly not Christian,
when championing the deprivation of anothers simple vote for the
hell of it.
------------------------------
From: "Andrew Vincze" <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt.random-numbers
Subject: Re: Fips Pub 140-1 and RNG
Date: Fri, 15 Dec 2000 08:19:53 GMT
<[EMAIL PROTECTED]> wrote in message news:90imdp$t3j$[EMAIL PROTECTED]...
> I have been looking at the FIPS PUB 140-1 and most specifically the
> power-up tests for random number generators.
> From my understanding, it looks more for the funcitonality of the RNG
> (e.g. the RNG is stuck) rather than its randomness but then again i
> might be totally wrong.
You are absolutely right. The number of bits necessary to *prove* an RNG is
truly random is infinite. As a practical matter, randomness to the degree
acceptable for a given application may be verified with a somewhat shorter
sequence, the length of which depends on the application.
20,000 is generally not enough to "certify" a new RNG, however it does
provide a useful tool for verifying that it is functioning prior to
generating a cryptographic key, which is much much shorter than 20,000 bits
in length - provided that the RNG has earlier been certified by more
thorough testing. You will also note the probability of a perfect RNG
failing FIPS 140-1 is about 1e-6. The failure criteria are intentionally
wide.
There are a number of good tests for randomness. Try Diehard. You can find
a link to diehard on the reference page on our web site,
http://www.rngresearch.com.
Good luck!
-Andrew Vincze
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: comp.sys.hp48
Subject: Re: Crypto Program for HP48GX Calculator
Date: Fri, 15 Dec 2000 08:12:04 GMT
Tom,
I am asking not to bother replying to my posts ever again because i
deduce for your replies is that you are an arrogant person and moreover,
you are very judgemental. You see things from you little point of view
and don't even take into account the world around you.
I don't doubt you capabilities in terms of cryptology as i think you
have quite an extensive knowledge. However you tend to forget that some
of us here don't necessarily have the time to do as much reserach and
invertigating as you in that field but are still interested in the
subject.
I have always been told that there is no point re-inventing the wheel
and indeed i believe. If i can find a piece of code that has already
been written and if it will give me more time to concentrate on other
issues then it is a good thing for me.
On the other hand, if you don't want to help, just keep quiet instead of
writting some pointless little comments that no one cares about. You are
wasting my time and others by doing so.
So come here and help. If you don't want to help or think you are too
good for some of us, create your own newsgroup and specify that it
should only be approached for people who have all the time in the world
to do solely cryptography and who know at least as much as you.
Regards,
Brice.
In article <91b1hf$4e2$[EMAIL PROTECTED]>,
Tom St Denis <[EMAIL PROTECTED]> wrote:
> In article <91ah7b$ldv$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] wrote:
> > Hi,
> >
> > I am looking for some crypto programs for the HP48GX. I am
interested
> in
> > DES and RSA but any other would be good too, the new AES algorithms
> for
> > example.
> >
> > Can anyone help?
>
> Why can't anyone do something for THEMSELVES! Try writting your own
> code and if you get stumped ask for help.
>
> For christ sake is everyone in this newsgroup incapable of their own
> work?
>
> Tom
>
> Sent via Deja.com
> http://www.deja.com/
>
Sent via Deja.com
http://www.deja.com/
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: comp.sys.hp48
Subject: Re: Crypto Program for HP48GX Calculator
Date: Fri, 15 Dec 2000 08:25:32 GMT
Indeed hpcalc.org is down but a mirror of it can be accessed at
http://wrc-1022.wrc.rice.edu/hp48/utils/security/.
Thank you all for your help or should i say for those who helped.
For the record, i can program and i can go and dig information for
myself, but time is money and when it is possible, i like to use what is
already available. So i thank those whose maturity level is high
enough to understand that.
In article <[EMAIL PROTECTED]>,
"Veli-Pekka Nousiainen" <[EMAIL PROTECTED]> wrote:
> <[EMAIL PROTECTED]> wrote in message
news:91ah7b$ldv$[EMAIL PROTECTED]...
> > Hi,
> >
> > I am looking for some crypto programs for the HP48GX. I am
interested in
> > DES and RSA but any other would be good too, the new AES algorithms
for
> > example.
> >
> > Can anyone help?
> >
> > Thank you,
> >
> > Brice.
> www.hpcalc.org look in the 48 utils security section
> (the site is down do I'm not sure about this)
> VPN
>
>
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Crossposted-To: comp.sys.hp48
Subject: Re: Crypto Program for HP48GX Calculator
Date: 15 Dec 2000 00:44:03 -0800
[EMAIL PROTECTED] writes:
> I am looking for some crypto programs for the HP48GX. I am interested in
> DES and RSA but any other would be good too, the new AES algorithms for
> example.
DES has been coded for the 48gx but RSA would be hopelessly slow unless
you're completely desperate. (If you code in Saturn machine language
it could be tolerable in some situations).
But I agree with Tom, the only point I can see of a program like this
on a 48gx would be to mess around with it for fun, and if that's what
you want it for, it's much more fun to write it yourself.
For a good algorithm for this purpose, see http://ciphersaber.gurus.com.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Protocol for computer go
Date: 15 Dec 2000 08:48:42 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
David Eppstein wrote:
>How is it prevented? The program in cheating-game-play mode has a variable
>that cycles through the possible moves, and when it sees a hint it waits
>until the variable comes round to the right move then outputs the move
>given by that variable.
That's prohibited, because the program must be a deterministic function
of the initial inputs and the moves of the other player.
If anyone questions the match ("some human helped!"), then you can produce
all the inputs (since they are determined in advance, and thus cannot be
controlled by a human, they can't be used by a human to control the output)
and then re-run the program, allowing others to verify that they get the
same output.
The crucial thing here is that the program compute a deterministic function
of the inputs, and that the inputs be verifiably free of human input. This
is how cheating is prevented.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Protocol for computer go
Date: 15 Dec 2000 08:50:07 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
David Eppstein wrote:
>Another commonly used method of cheating is for a human operator to watch
>the computer's display of what move it is currently planning to make, and
>use the "move now" command when you like the move you see.
Yes, the termination condition is a side input that a human could control.
Hence, this type of termination condition must be prohibited.
So long as the termination time is a deterministic function of the inputs
(and the inputs are verifiably free of human control), this is not a problem.
If the computer is remote, you can tell, because the algorithm and the inputs
will be disclosed, so you can re-run them on your own machine.
------------------------------
Subject: DUKPT using Triple DES
From: [EMAIL PROTECTED] (Mark Currie)
Date: 15 Dec 2000 08:52:20 GMT
Hi,
The VISA Derived Unique Key Per Transaction (DUKPT) method has some useful key
management features but I only have the original VISA spec (1988) which uses
single DES.
Does anyone know if there is an ANSI/ISO equivalent ? I searched both sites
with no success.
Are there any standard versions that use Triple DES instead of single DES ?
Thanks
Mark
------------------------------
From: "Brian Gladman" <[EMAIL PROTECTED]>
Subject: Re: Unguessable sequence of unique integers?
Date: Fri, 15 Dec 2000 09:14:00 -0000
"Bryan Olson" <[EMAIL PROTECTED]> wrote in message
news:91brlg$qfr$[EMAIL PROTECTED]...
> Brian Gladman wrote:
> >
> > Maybe, John, but as you have just pointed out elsewhere, implicit
> > assumptions are likely to put us on dangerous ground :-)
>
> I do not think it would have made sense to bloat the post with
> assumptions unrelated to the issue in question.
>
> Savard wrote that he'd have a hard time believing the
> technique could be secure with a 32-bit block. I disagreed.
> If you are saying it can't be secure with a short key, then I
> agree, but that's a different issue. Are there some
> techniques to generate the stream from short key that are
> secure?
Not that I am aware of, and this was my point. My aim was hence to do two
things (1) to make the need for a long key explicit, and (2) to ask if there
are any practical limitations on the maximum effective key length arising as
a result of the small block length in the context set by this application
(i.e. a 32-bit 'random' sequence generator).
I considered this to be related to the issue in question since I believe the
'issue' to be the security needed to protect the 'unguessability' of the
sequence. My specific concern was (and is) that of any practical constraints
that the short block length might place on the maximum length of effective
keys as permutation selectors.
I wondered whether ciphers would necessarily be good permutation
'selectors' - that is, are keys likely to select permutations that are
spread sufficiently uniformly across the permutation space available?
> > I hence wanted to make this assumption explicit and
> > hence to pose the question of the possible security
> > limitations that come with short block, long key ciphers.
>
> Are you asking if the security could be adequate for use as a
> general purpose cipher, or to solve the problem that is the
> subject of this thread?
No to the first, yes to the second.
Brian Gladman
------------------------------
From: Anders Thulin <[EMAIL PROTECTED]>
Subject: Re: security by obscurity ...
Date: Fri, 15 Dec 2000 09:26:01 GMT
Peter Thorsteinson wrote:
> It is often said that security by obscurity is not a valid approach.
There are many forms of that utterance now, and I'm not sure
which is be considered to be the original one or the correct one.
Indeed, it is in danger of coming close to be treated as a mantra -- to
be repeated with as little conscious thought as possible.
My interpretation of it is that obscurity is not sufficient for security.
It may be a component of security, but it should not be the only component.
And if it *is* such a component, the value of that obscurity should be
analyzable and expressed in some security-related terms, such as time or cost.
But that's just my opinion.
> However, I cannot see a fundamental difference between using an algorithm
> that is difficult to guess, and a key that is difficult to guess (due to
> large name space and uniform probability distribution).
If the key is secret, and the algorithm sound, you can estimate the time
that gives you fairly well -- the time required to crack the key by best
effort methods. You know where you are.
If the algorithm is sound but secret, you add an amount of time to that
cracking effort. How much, you don't know. If the secret is well kept,
you get the full time advantage. But should it be betrayed, you lose
it all, and retain only the secret key 'time'. And you usually don't
learn beforehand when secret algorithm become known.
This works as long as you do not rely on the extra time, but treat it as
a bonus, and provided you can ensure that the algorithm is sound.
You very seldom can do so without imparing the secrecy, and so lose
most of the advantage that that secrecy gave you. So it seems to be
less useful to try to have a secret algorithm.
If the secret algorithm happens to be unsound, it may jeopardize also the
time advantage inherent the secret key. The loss of time advantage here cannot
be estimated, as the unsoundness usually is not known. The opportunity
for serious loss is obvious.
The loss of one key affects only the communication protected by that key.
The loss of a sound but secret algorithm doesn't change that -- the
security is still in the key. The loss of a secret algorithm that is
less than sound may affect all communication protected by this algorithm.
It's all risk management: what do we know for sure and can rely on, and
what won't we know and can't possibly rely on. And if the worst happens,
how do we restrict damage as much as possible.
--
Anders Thulin [EMAIL PROTECTED] 040-10 50 63
Telia ProSoft AB, Box 85, SE-201 20 Malmö, Sweden
------------------------------
From: Kirk Whelan <[EMAIL PROTECTED]>
Subject: Possibly Another Encryption Method - Any Thoughts ?
Date: Fri, 15 Dec 2000 09:34:42 +0000
Hi everybody, as a result of watching this thread for a while,
and seeing the invites to see if things can be cracked.
I would like to ask for comments on a security encryption method that I
have been working on.
So people would like to see the plain text and the cyphertext,
OK
Here are a few instances of my name "Kirk" being encoded,
I have kept it short to ease the deciphering.
a9n09100p8dGdama8ck3
U500o3T6hR46H4R
m5z5d4L0oigXK0lgM0eh
BWvT6Jvo7ud
and a few instances of my phone number 01784436234
LVQ7bOa0jXpaus50Tvq6V36Cv5l57k53Pji
z4MY0h567x5Uv5DMxc55SBP7yKF04470gXkiXR9
D7caHRRa35GXa92BS19Yo21bpa3jf
OK, a few clues, nothing new in innovation just application.
Fractionalisation in first and last stage.
Enigma wheels and primes that's it.
Oh I have done nothing to disguise frequency of letters at this stage.
3 random digits to produce the variations
A couple of clues as a base number and two simple formulae where used.
Any takers.
Kirk Whelan
------------------------------
** 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
******************************
