In need of an EllipticCurve example (jdk1.5)

[Oliver Wong]

You don't have to trust Fedex at all. What you have to trust is that
you can wrap a package is such a way that you can detect if it has
been opened.

Okay, true. But I claim it is less fallacious to trust FedEx than to
trust that you could wrap a package in such a way that you could detect if
it has been opened. Especially since it isn't YOU who is opening the
package, but rather your recipient.

That is to say, you're wrapping your package in some specific way, and
sending it to the recipient.

Now the recipient receives a package. How does she know she got the same
package as the one you sent? Well, I guess you would have to describe to her
(in clear text?) how your package was wrapped, and what revealing signs to
look for, for evidence of tampering.

You don't even have to do that. You just need to know the that
probability of the package being intercepted is less that some bound
b.

They can only hurt you if they intercept ALL your packages undetected.

It is the inverse of my floppy disk scheme for recovery from scratches
and thumbprints that Norton Backup used. If a sector is lost from a
mutually protective set, you can recreate it by xoring the remaining
ones. However, if any of the remaining ones is also missing, you
can't.

Yes, also true, though calculating b (or enforcing b) can be very
"non-trivial".

- Oliver

 

[Bent C Dalager]

The problem with one-time pads is that when you re-use them, you're not
only sacrificing the security of the old message, but of the new message as
well!

If the only alternative would have been clear text, then you're not
actually sacrificing anything wrt the new message.

Transmitting in the clear may be better in some cases. I believe there's
a famous quote in the cryptanalyst circles that goes something like
(paraphrased): The only thing worse than no security is a false sense of
security.

That is a different question though. The security inherent in using
otp with ttp fallback is calculable, and it's better than zero.
Whether you are able to successfully educate your field operatives as
to the quality of your crypto system is another matter entirely.

Cheers
Bent D

 

[Chris Uppal]

The security inherent in using
otp with ttp fallback is calculable, and it's better than zero.

Since exploiting TTP requires that the atacker be able to recognise and use
correlations between the two plaintexts, it seems as if even a very simple
hand-cranked encryption could be applied to the second plain text before
pushing it through the OTP and make it significantly harder to crack.

-- chris

 

[Bent C Dalager]

Since exploiting TTP requires that the atacker be able to recognise and use
correlations between the two plaintexts, it seems as if even a very simple
hand-cranked encryption could be applied to the second plain text before
pushing it through the OTP and make it significantly harder to crack.

Perhaps, but it could also be that the increased cryptoanalytic burden
achieved fails to compensate for the added risk of making encryption
errors in the extra step.

Additionally, part of the attraction of OTP in the first place was the
rather trivial algorithm for doing manual encryption (although as I
recall, they actually added complexity in order to save money on
telegrams for some reason - spies on a budget?). Adding an extra layer
for the occasional TTP use might simply be too complex for practical
field use.

Cheers
Bent D

 

[Scott Ellsworth]

If the only alternative would have been clear text, then you're not
actually sacrificing anything wrt the new message.

One subtlety - the re-used pads were used for low security messages as
well as high security messages. Thus, the much more voluminous low
security messages ended up being a crack for the more valuable high
security ones.

Scott

 

[Bent C Dalager]

One subtlety - the re-used pads were used for low security messages as
well as high security messages. Thus, the much more voluminous low
security messages ended up being a crack for the more valuable high
security ones.

It's been a while since I read about this so many details are long
gone. Are you saying that they reused the same page three, four, five
and even more times?

Cheers
Bent D

 

[Roedy Green]

The gist is that the Soviets re-used some pages of
their one-time pads -- not the entire pads, just a page

I think that is much less of a problem. I think I could write
software that even on crash would never reusa a pad. Further with CDs,
there is no shortage of random gibberish. It is not precious the way
it would have been on paper.

To make sure you never reuse a key, you load your CD worth of keys
onto hard disk, and destroy the CD. Then as you use parts of the pad
you wipe it multiple times, both to prevent someone stealing the
computer from cracking old messages, and to prevent reuse of keys.

IF someone steals your computer the bad guys can only crack the
message in transit at the time, plus of course whatever clear text you
leave lying about.

 

[Chris Uppal]

Bent C Dalager wrote:

[me:]

Perhaps, but it could also be that the increased cryptoanalytic burden
achieved fails to compensate for the added risk of making encryption
errors in the extra step.

Additionally, part of the attraction of OTP in the first place was the
rather trivial algorithm for doing manual encryption (although as I
recall, they actually added complexity in order to save money on
telegrams for some reason - spies on a budget?). Adding an extra layer
for the occasional TTP use might simply be too complex for practical
field use.

Both are quite plausible, but I meant only that a layer of (simple) encryption
be added to the second use of the pad. I.e. when we start running out of pads,
and have to fall back to sending in clear or re-using, we then (and only then)
start using encryption too.

Assuming that the OTPs are just XORed with the plaintext, we only need an
encryption algorithm, Enc, with the property that:

p1 XOR Enc(p2)

(where p1 is the first plaintext, and p2 is the second)

should leak usefully less information to the adversary than just:

p1 XOR p2 [*]

or, if we don't reuse at all:

p2

I'm no cryptologist, but it seems to me likely that such schemes exist, and
exist in forms that are simple enough for real people to calculate by hand, or
with cheap and very simple to use, emergency fall-back kit. Especially since
there is a very high quality source of random seeds available in the unused
trailing bytes of previous OTPs.

-- chris

[*] I once, btw, looked at decoding programming language text where the source
of several methods had been encoded with the same OTP, it turned out that there
was more than enough info encoded in the XOR of just two methods to recover the
entire text of the shorter of them. Of course, it does depend on the coding
style, and programming language -- I wouldn't care to try the same trick with
Perl ;-)

 

[Eric Sosman]

Roedy Green wrote On 03/07/06 02:32,:

I think that is much less of a problem. I think I could write
software that even on crash would never reusa a pad. Further with CDs,
there is no shortage of random gibberish. It is not precious the way
it would have been on paper.

Keep in mind that mere "random gibberish" is not enough:
What's needed is R.G. that's an exact duplicate of the R.G.
at the other end of the encrypted communication. Once the
existing supply of R.G. is exhausted, the two ends cannot
just make more gibberish and keep on chatting[*]; they must
communicate a new batch of R.G. through some other channel.
That channel is cumbersome and potentially vulnerable --
and no, OTP wouldn't help on the second channel (infinite
regress).

[*] Well, the two sides could have agreed on a pre-
arranged algorithm for generating gibberish. But then it's
no longer an OTP code: anybody who cracks or guesses or
steals the R.G. generator has you at his mercy. Besides
which, deterministic gibberish is (so I've read) relatively
easy to cryptanalyze. You need those radioactive samples
or Lava Lamps or whatever -- and their rate of production
of uncorrelated noise is not infinite ...

To make sure you never reuse a key, you load your CD worth of keys
onto hard disk, and destroy the CD. Then as you use parts of the pad
you wipe it multiple times, both to prevent someone stealing the
computer from cracking old messages, and to prevent reuse of keys.

It seems to me that by making a second (third, really)
copy of your most precious secret, you have diminished rather
than enhanced security. It seems to be rather difficult to
erase things from a magnetic medium, no matter how many times
you overwrite it or how cleverly you choose the overwriting
patterns. I'm told (by my old pal from the spook shop) that
the approved procedure for wiping classified information from
a drive involves an incinerator.

IF someone steals your computer the bad guys can only crack the
message in transit at the time, plus of course whatever clear text you
leave lying about.

Or, if they can recover the "erased" data, everything you
ever encoded with that OTP.

 

[Oliver Wong]

Roedy Green wrote On 03/07/06 02:32,:

I think that is much less of a problem. I think I could write
software that even on crash would never reusa a pad. Further with CDs,
there is no shortage of random gibberish. It is not precious the way
it would have been on paper.

Keep in mind that mere "random gibberish" is not enough:
What's needed is R.G. that's an exact duplicate of the R.G.
at the other end of the encrypted communication. Once the
existing supply of R.G. is exhausted, the two ends cannot
just make more gibberish and keep on chatting[*]; they must
communicate a new batch of R.G. through some other channel.
That channel is cumbersome and potentially vulnerable --
and no, OTP wouldn't help on the second channel (infinite
regress).

I was confused by Roedy's post at first too. I think what he means is
that imagine you somehow received a CD which contains the OTP to use (and so
did the person you wish to communicate with). From that point on, how could
you ensure you never re-use a pad (and Roedy's solution is to copy the CD,
break the CD, and run special software, etc.)

We're now getting into issues of writing a secure OS as well (no
Microsoft jokes please). An unsecure OS may be caching the key in a virtual
memory file.

If you're the originator of the OTP, you would probably generate the OTP
on a file, and then burn it onto a CD. Well, now you have to ensure that the
buffers in your CD burner are cleared after the burning process is done.
Maybe that's controlleable from the OS, or maybe you have to write special
device drivers, or maybe even build your own custom CD burner to get that
facility.

For the extremely paranoid, you'd want to enclose your working
environment in a faraday cage, so that attackers (outside of your working
environment) could not monitor electromagnetic waves being emitted by the
CPU, RAM, or other components of your computer, and try to detect what
sequence of operations it is performing (known as a TEMPEST attack).

The National Institute of Standards and Technology (NIST, as US
organization) published a Federal Information Processing Standards
Publication called FIPS PUB140-2 titled "Security Requirements for
Cryptographic Modules". I stumbled over a while ago while going through the
NIST archives researching something unrelated.

Post a summary of it on my blog, intended for the Military Otakus:
http://nebupookins.net/entry.php?id=240

It seems to me that by making a second (third, really)
copy of your most precious secret, you have diminished rather
than enhanced security. It seems to be rather difficult to
erase things from a magnetic medium, no matter how many times
you overwrite it or how cleverly you choose the overwriting
patterns. I'm told (by my old pal from the spook shop) that
the approved procedure for wiping classified information from
a drive involves an incinerator.

I had a non-programmer (i.e. "normal person") friend who asked me if you
could corrupt the contents of a hard drive using a magnet. The question as
ambiguous: I wasn't sure if she was asking whether it was safe to have
magnets lying around near the harddrive, or whether she was asking if she
could evade the FBI/CIA/whoever else just by waving magnets around her
harddrive. The answer to the two questions might seem, at first, to
contradict each other!

So I told her this, and she told me I wasn't answering her question. So
I asked her what her question was, and she repeated the same ambiguous
question. I spent maybe 2 hours trying to explain to her why it was
ambiguous, and I gave her the above two questions, and tried asking her
which one her question was more similar to, all to no avail. To this day,
she still doesn't know the answer to her question, and I still don't know
what question she was asking.

Or, if they can recover the "erased" data, everything you
ever encoded with that OTP.

Security is all about making it more expensive for the attackers to run
their attack than how much they would gain from succeeding. If you have a
$10'000 secret hidden on your laptop, but it costs $50'000 to recover the
erased data to get at that secret, it's not worth it for your attackers to
pursue this route.

- Oliver

 

[Roedy Green]

You need those radioactive samples
or Lava Lamps or whatever -- and their rate of production
of uncorrelated noise is not infinite ...

I think the gibberish supply is pretty well inexhaustible. You can buy
a radioactive random number generator quite cheaply now.
see http://mindprod.com/jgloss/truerandom.html

You could tape FM hiss. I suppose bad guys could fool you by
broadcasting an FM broadcasting hiss station if they knew the
frequency you were sampling.

 

[Roedy Green]

that

I read that then a drive fails in the navy, it is destroyed. The
security risk of allowing it to be repaired is too great. I suppose
this is not nearly such a surprise now that drives are so much
cheaper.

 

[Roedy Green]

You could tape FM hiss. I suppose bad guys could fool you by
broadcasting an FM broadcasting hiss station if they knew the
frequency you were sampling.

My original version of the algorithm was written on the Apple ][ and
used the Mexican peasant algorithm.

See http://mindprod.com/products3.html#ENCODE

 

[Eric Sosman]

Roedy Green wrote On 03/07/06 12:36,:

You need those radioactive samples
or Lava Lamps or whatever -- and their rate of production
of uncorrelated noise is not infinite ...

I think the gibberish supply is pretty well inexhaustible. [...]

Take Usenet, for example. ;-)

 

[James McGill]

Mexican peasant algorithm.

Okay, I'll bite. Why is it called that?

 

[Roedy Green]

Okay, I'll bite. Why is it called that?

I figured it might become a third world cottage industry creating
one-time pads in sweat shops. People pound away on keyboards. It does
ot matter what they type, just the microtiming.

 

[The_Sage]

Date written: Thu, 02 Mar 2006 14:34:16 GMT
MsgID:<InDNf.11710$dg.2838@clgrps13>

I'd figure the biggest problem is getting the key to the intended
recipient without a man-in-the-middle attack.

My recommendation is to stick with traditional (quantum-weak) encryption
for now, and when quantum computing becomes available, switch to quantum
encryption (which is currently believed to be impossible to crack; not
"merely" infeasible to crack).

Quantum encryption is a misnomer, it is actually just quantum modulation. The
sole purpose of using so-called quantum encryption is to be able to detect when
someone has intercepted your message. I don't need to know the state of both
entangled photons in order to know what the message sent was, but by
intercepting just one message, I've prevented both recipients from ever
receiving the message, thereby alerting the recipients to a spy. This is also
called jamming. In fact, I don't even have to read your message in order to
scramble your quantum communications, all I have to do is attempt to read it. If
I simply count the number of photons as they pass, the entanglement property is
lost.

In order for quantum encryption to work, there must be three parties present
during any transmission: the sender and two receivers. Traditional encryption
only requires two: the sender and the receiver. This both complicates and limits
the usefulness of the method. Quantum encryption is limited to sending two
entangled photons at a time -- one photon for each data bit, for each receiver.
Traditional encryption can send billions of photons at a time for each data bit.
The signal-to-noise ratio would therefore be horrendous for quantum encryption.

Let's imagine we could send two little photons, all by themselves, hundreds of
kilometers through space and into meters of seawater. That is very unlikely but
we are just pretending here. The problem is this: Gen Patton sends a quantum
encrypted message to Pvt Bob and Pvt Alice, each of which are located in
different submarines miles apart. In order to read the message, Bob and Alice
must talk to each other afterwards in order to reveal their correlations, but in
doing so they will give away their positions. Traditional encryption requires no
such public two-way communications.

Let's say Gen Patton wants to keep the location of one of the submarines secret,
so he sends both photons to that one submarine that happens to contain two
different receivers. Well that eliminates the need for the two-way public
broadcast to determine if the message was intercepted, but Gen Patton has still
inadvertently given away the location of the submarine because the path the two
photons take will help triangulate it's location.

The point is if you want to have secure communications, use a good encryption
algorithm. Elliptic crytography is good. Go here http://libecc.sourceforge.net/
and here http://www.cs.may.ie/~aburnett/rajt02.pdf to learn how to implement ECC
in Java.

The Sage

=============================================================
http://members.cox.net/the.sage/index.htm

"Little minds are interested in the extraordinary; great
minds in the commonplace"
-- Elbert Hubbard, ROYCROFT DICTIONARY AND BOOK OF EPIGRAMS
=============================================================

 

[Oliver Wong]

I figured it might become a third world cottage industry creating
one-time pads in sweat shops. People pound away on keyboards. It does
ot matter what they type, just the microtiming.

Russia tried this, I believe. It was disastrous. Humans aren't good at
being intentionally random.

Can't find a citation now, but basically they instructed secretaries to
just randomly punch keys on the typewriters. There were inherant patterns in
the typing which the Americans picked up and thus managed to crack all the
messages being sent without Russia being aware of it.

- Oliver

 

[Oliver Wong]

Quantum encryption is a misnomer, it is actually just quantum modulation.
The
sole purpose of using so-called quantum encryption is to be able to detect
when
someone has intercepted your message. I don't need to know the state of
both
entangled photons in order to know what the message sent was, but by
intercepting just one message, I've prevented both recipients from ever
receiving the message, thereby alerting the recipients to a spy. This is
also
called jamming. In fact, I don't even have to read your message in order
to
scramble your quantum communications, all I have to do is attempt to read
it. If
I simply count the number of photons as they pass, the entanglement
property is
lost.

Yes, when I said "quantum encryption", I was specifically thinking of
using OTPs, but using what you call "quantum modulation" for key exchange.
I.e. the composite of all those steps together is what I meant by "quantum
encryption".

In order for quantum encryption to work, there must be three parties
present
during any transmission: the sender and two receivers. Traditional
encryption
only requires two: the sender and the receiver. This both complicates and
limits
the usefulness of the method. Quantum encryption is limited to sending two
entangled photons at a time -- one photon for each data bit, for each
receiver.
Traditional encryption can send billions of photons at a time for each
data bit.
The signal-to-noise ratio would therefore be horrendous for quantum
encryption.

Let's imagine we could send two little photons, all by themselves,
hundreds of
kilometers through space and into meters of seawater. That is very
unlikely but
we are just pretending here. The problem is this: Gen Patton sends a
quantum
encrypted message to Pvt Bob and Pvt Alice, each of which are located in
different submarines miles apart. In order to read the message, Bob and
Alice
must talk to each other afterwards in order to reveal their correlations,
but in
doing so they will give away their positions. Traditional encryption
requires no
such public two-way communications.

Let's say Gen Patton wants to keep the location of one of the submarines
secret,
so he sends both photons to that one submarine that happens to contain two
different receivers. Well that eliminates the need for the two-way public
broadcast to determine if the message was intercepted, but Gen Patton has
still
inadvertently given away the location of the submarine because the path
the two
photons take will help triangulate it's location.

I've never heard of this scheme you're describing now. Here's what I was
envisioning:

So Alice wants to communicate with Bob, and Charlie wants to intercept
the message. Alice says openly "Be sure to gather 1024 random bits." She
chooses some big number which is not associated with her message (because
she doesn't want Charlie deriving the contents of the message from the size
of the message).

Alice starts sending some photons. Charlie intercepts some. Bob can
detect the ones that got intercepted, so he throws them away. Charlie misses
some of the other ones. Bob receives these bits and can tell they were not
intercepted. He waits until he has 1024 of them, then openly says "Okay
Alice, I've got 1024 bits."

Alice, meanwhile, has been recording all the bits she's been sending.
Bob told her to stop, so she stops. Bob then openly tells her "Okay, the 1st
bit was intercepted by Charlie, the 2nd bit was not, the 3rd bit was not,
the 4th bit was, etc." So Alice discards all the bits that Charlie
intercepted. Now she has the 1024 bits that both she and Bob know and that
Charlie doesn't.

Alice says openly "okay, use those 1024 bits as the OTP pad. Here's the
encrypted message." Charlie has no way of decrypting the message from the
bits he did intercept, and from all the open communication that was done.

As for the secret-location of submarines etc., I consider that to be a
seperate concern than simply encrypting messages, and so it wasn't addressed
at all in this post of mine.

- Oliver

 

[Bent C Dalager]

Alice, meanwhile, has been recording all the bits she's been sending.
Bob told her to stop, so she stops. Bob then openly tells her "Okay, the 1st
bit was intercepted by Charlie, the 2nd bit was not, the 3rd bit was not,
the 4th bit was, etc." So Alice discards all the bits that Charlie
intercepted. Now she has the 1024 bits that both she and Bob know and that
Charlie doesn't.

If this message is transmitted in clear, how do you prevent Charlie
from intercepting the message and replacing it with his own?

Cheers
Bent D