Efficent Digital Signature Schemes.....
Paul
Can someone recomend a good digital signature scheme?
Requirements:
Signature algorythim must be computationally easy.
(running on low power micro with minimal RAM)
Verfication algorythim will run on a pentium class PC.
Signature data storage must not be more than 256 bytes or so.
Needs to be about as secure as RSA with a 512 bit key.
Paul
Paul Crowley
Is it running on a smart card?
It sounds like DSA-512 would be an exact fit. The group parameters
take 64*2+20=148 bytes of storage in total, and the private key a further 20
bytes. You can safely share the group parameters between all users if
you have more storage in a shared ROM than in non-volatile storage.
You can also use "precomputation" for very fast signing. See
"Applied Cryptography" for details.
--
__ Paul Crowley
\/ o\ s...@paul.ciphergoth.org
/\__/ http://www.ciphergoth.org/
Paul
>Is it running on a smart card?
No it would be logging:
GPS based position
altitude data (both pressure and GPS)
It is a tool for recording Sailplane flights in a way that
is secure, for FAI soaring badges, contests and even world records!
The private key is stored inside a sealed unit with a barometer port
and GPS receiver.
It spits out a data record with a digital signature.
The public key is widely distributed as a software tool,
it must be able to verify that a data file generated by the sealed
unit has not been modified.
If you had control of both ends of the link you could seed a hash with
some secret and a random seed and use that, but the
secret would then be availible to anyone that could disasemble the
widely given out software tool.
Paul
Paul Rubin
> No it would be logging:
> GPS based position
> altitude data (both pressure and GPS)
>
> It is a tool for recording Sailplane flights in a way that
> is secure, for FAI soaring badges, contests and even world records!
>
> The private key is stored inside a sealed unit with a barometer port
> and GPS receiver.
Put one of these into the unit:
http://www.ibutton.com/ibuttons/java.html
They are physically pretty secure, don't need much power, and can
do a 1024 bit RSA signature in about 1 second.
Scott Contini
Of the three most accepted signature algorithms (ECDSA, DSA, and RSA),
it appears that you are looking for ECDSA. If you are using a processor
that doesn't have a fast 32-bit multiply, then choose ECDSA over GF(2^m),
preferably with trinomial basis. 512-bit RSA security is equivalent to
ECC over approximately 128-bit field sizes. Let's see: GF(2^127) seems
to be a good choice since you can use the trinomial x^127 + x + 1 for your
irreducible polynomial. Some people might argue that you can get away
with a smaller field size for that level of security, but I wouldn't go
too much smaller.
Here is a little "cheat sheet" on what signature algorithm to use for
various circumstances:
RSA: use when fast verifications are critical and when signature sizes and key
sizes are not important.
ECDSA: use when signature and key sizes must be small, or when on very
constrained devices that do not have fast 32-bit multiplies, or when
signature speed is much more important than signature verification speed
and approx 7K or more of RAM is available to speed signatures using
precomputation methods.
DSA: use when signature sizes must be small, and if you don't trust
ECC.
Scott
Paul Crowley
> >Is it running on a smart card?
>
> No it would be logging:
> GPS based position
> altitude data (both pressure and GPS)
>
> It is a tool for recording Sailplane flights in a way that
> is secure, for FAI soaring badges, contests and even world records!
>
> The private key is stored inside a sealed unit with a barometer port
> and GPS receiver.
>
> It spits out a data record with a digital signature.
> The public key is widely distributed as a software tool,
> it must be able to verify that a data file generated by the sealed
> unit has not been modified.
How come you only need the same security as RSA-512, in that case?
The first public 512-bit factorization was completed nearly four years
ago; these days it doesn't offer that much protection. DSA is based
on a different hard problem, discrete logarithm, but it turns out that
the current best algorithm against factorisation is also the current best
against discrete log, so they're currently roughly as hard as each
other. I'd recommend at least 768 bits if you want to be secure for
just a few years.
Note also that tamper resistance/tamper evidence is Really Hard. If
you haven't read Ross Anderson's "Security Engineering", it is
*essential* that you do so.
You'll need a high-quality RNG. Look at the design of Yarrow;
obviously AES can be substituted in place of Triple-DES.
I would certainly recommend very strongly that every unit have a
different private key which it generates itself and never reveals, and
that the public key then be signed by the manufacturer along with
information about its manufacture. As I said before, group parameters
can be shared.
Incidentally, I'm sure you've thought of this, but record and sign the
raw GPS data, not the converted coordinates. That way you can correct
for ionospheric distortion by applying DGPS after the fact...
You'll still be vulnerable to attacks from GPS jammers of course.
Can I persuade you to provide a spam-trapped email address in your
.sig? I understand why you don't want to provide it where spammers
can get it, but it's polite to provide an address for humans.
Michael Amling
IIRC, a Zheng signature for ECC is about 50% longer than the number
of bits in the ECC field. If you used, say, a 128-bit field, security
would be comparable to a 512-bit RSA, and the signature would be about
24 bytes.
--Mike Amling
Paul Rubin
> You'll still be vulnerable to attacks from GPS jammers of course.
This is a very important point. You're vulnerable not only to jammers
but also to spoofers. Anyone with the right off-the-shelf GPS test
equipment can send a false signal that convinces your module's GPS
receiver that it's in Bolivia at 30,000 feet or wherever else the
cheater wants to pretend to be.
Paul
>
>How come you only need the same security as RSA-512, in that case?
>The first public 512-bit factorization was completed nearly four years
>ago; these days it doesn't offer that much protection.
The FAI specification specifies RSA-512.
I Agree it could be better.
Also the individualt Private keys signed by the public key makes a lot
of sense, but then I've got to include both the public key,
the key signature and the actual data signature in the verification
data block. Still do able....
Removing all formating and excess stuff....
Individual public key 1024,
Signature of key 1024
Signature of digest 1024
This is 384 bytes a fair bit of data.
>Can I persuade you to provide a spam-trapped email address in your
>.sig? I understand why you don't want to provide it where spammers
>can get it, but it's polite to provide an address for humans.
IS this sig better?
Paul
Replace null.org with
ROMEO ALPHA SIERRA DELTA OSCAR CHARLIE dot CHARLIE OSCAR MIKE
Paul
An offical observer must witness that the logger is sealed to the
glider. Another official observer must verify that it is still sealed
to the glider and witness the download from the unit to a pc.
The observer then sends the data in......
An official observer must also either witness the takeoff or landing.
In addition to the GPS flight log, the unit also has a barametric
pressure sensor so the altitude also matches the GPS altitude.
The vast majority of these are used for gaining FAI achievement badges
and local contests. IT is quite rare that one would actually be used
for a world record. And in the world record case there would probably
have to be additional supporting evidence.
(The current world distance record is 3018km in a glider, done over
the mountains in south america in done this last December or January)
Paul
On 21 Feb 2003 17:06:42 -0800, Paul Rubin
<http://phr...@NOSPAM.invalid> wrote:
Replace null.org with
Gregory G Rose
It seems to me (from reading this and other
responses) that you've asked the wrong question.
What you want to do is have the machine add
entries to a log, and then, when it's ready to
spit out the log, hash it and digitally sign the
hash. Only one PK operation, and that's at the
end of the day...
Greg.
--
Greg Rose INTERNET: g...@qualcomm.com
Qualcomm Australia VOICE: +61-2-9817 4188 FAX: +61-2-9817 5199
Level 3, 230 Victoria Road, http://people.qualcomm.com/ggr/
Gladesville NSW 2111 232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C
Zulfikar Ramzan
Given that you have 256 *bytes* for storage but only require the
security of 512-bit RSA, why not just use RSA with a public exponent
amenable to faster signature computation (e.g. e = 3 or 17 or 65537)?
A faster possibility is the use of Rabin signatures (where a modular
squaring operation is performed). BTW, a 512-bit modulus is considered
very small by today's standards, so you really may want to think about
using something larger.
Yet another option is the use of an elliptic-curve based system such
as the elliptic curve analog of the digital signature algorithm
(google "elliptic curve digital signature" for a lot of links). Here
the key length is shorter than what is needed for traditional RSA,
Rabin, or DSA while seeming to offer comparable security (based on
what's currently known about the intractibility of solving various
problems related to elliptic curves). Companies like Certicom are
championing their use, especially for resource-constrained devices.
In all of these cases, there are a host of implementation issues to
consider (and a million places where it's possible to mess things up)
especially with respect to payload padding and pre-processing,
protocol assumptions, timing, and so on; one would need a lot of space
to expound upon all of these issues.
I would therefore strongly urge you to follow a specific standard
closely or leverage an implementation that has been vetted.
Hope this helps!
-- Zulfikar Ramzan
Paul <donts...@null.org> wrote in message news:<d1mc5vcptk55fuuff...@4ax.com>...
David Wagner
>Given that you have 256 *bytes* for storage but only require the
>security of 512-bit RSA, why not just use RSA with a public exponent
>amenable to faster signature computation (e.g. e = 3 or 17 or 65537)?
>A faster possibility is the use of Rabin signatures (where a modular
>squaring operation is performed).
You've got it backwards. A smaller exponent -- or Rabin's method --
only speeds up verification, not signing, and the original poster asked
for signing to be cheap (verification was to be done on a Pentium).
El Gamal may be nice in that it allows a message-independent
pre-computation of a "blank check"; later, when you know what message
you want to sign, you can fill in the "blank check" with the details of
the message and thereby obtain a valid signature using just one or two
modular multiplications.
Paul
wrote:
>t seems to me (from reading this and other
>responses) that you've asked the wrong question.
>What you want to do is have the machine add
>entries to a log, and then, when it's ready to
>spit out the log, hash it and digitally sign the
>hash. Only one PK operation, and that's at the
>end of the day...
Yes that is true, I'd like to be able to do this on the same processor
that just ran for 18 hours on a single small battery.
I don't care if it takes 20 seconds to compute the RSA signature,
but the thought of developing the whole RSA system complete with
monty modular math etc on a very small very limited low power device
is a huge task (for me anyway) I've previously ported RSA code to a 32
bit embedded system, and the thought of doing that on something like a
low resource 8 bit device seems to be a daunting task.
This digital signature is the only place in the whole system where any
computational horsepower is required, and so it sets the lower limit
for the computational resources necessary.
Does anyone make a 1024 bit modular multiplier as a small cheap add on
chip? The Java I Botton looks cool, but it is about >$40.00 in small
quantiites and would account for a significant portion of the total
bill of material.
These FAI loggers exist in the $800+ range today, I want to try to
build one that is more affordable.
Paul
Paul Rubin
> Does anyone make a 1024 bit modular multiplier as a small cheap add on
> chip? The Java I Botton looks cool, but it is about >$40.00 in small
> quantiites and would account for a significant portion of the total
> bill of material.
There are smart card chips in the $5 range that can do RSA signatures
but don't have as many features or as much security as the Java
button. Or the box on the plane could just spit out a hash encrypted
by a secret key. The hash would then be decrypted and signed by a
separate computer held by the certifying organization.
See www.basiccard.com for some smart card stuff that's easy to develop
with and is fairly cheap in small quantity.
Paul Crowley
> El Gamal may be nice in that it allows a message-independent
> pre-computation of a "blank check"; later, when you know what message
> you want to sign, you can fill in the "blank check" with the details of
> the message and thereby obtain a valid signature using just one or two
> modular multiplications.
DSA has the same property, of course. I assume ECDSA does also; I
don't know ECDSA, am I right in assuming it's basically DSA done over
an elliptic curve based group instead of a Schnorr group?
Anne & Lynn Wheeler
> Is it running on a smart card?
>
> It sounds like DSA-512 would be an exact fit. The group parameters
> take 64*2+20=148 bytes of storage in total, and the private key a further 20
> bytes. You can safely share the group parameters between all users if
> you have more storage in a shared ROM than in non-volatile storage.
> You can also use "precomputation" for very fast signing. See
> "Applied Cryptography" for details.
is hardware token that does fips186-2/x9.62/ecdsa signatures
disclaimer ... this is the AADS chip strawman that i've been going on
about for some number of years.
http://www.garlic.com/~lynn/index.html#aads
--
Anne & Lynn Wheeler | ly...@garlic.com - http://www.garlic.com/~lynn/
Internet trivia, 20th anniv: http://www.garlic.com/~lynn/rfcietff.htm
Bryan Olson
> I don't know ECDSA, am I right in assuming it's basically DSA
> done over an elliptic curve based group instead of a Schnorr
> group?
More or less. It's just El Gamal, except using a group of
points on an elliptic curve instead of Z*_n. The groups chosen
always have prime order.
--
--Bryan
DJohn37050
DSA or RSA. Of course the hash is the same for all 3.
Don Johnson
Gregory G Rose
Another alternative is to use DSA rather than RSA.
You can make use of the fact that most of the
signature computation can be done *before* the
data is available for signature. So you don't care
if your cheap-as-dirt 8 bit CPU spends an hour of
its spare time using a very straightforward
algorithm precomputing the signature (while
doing the logging as required), then just a single
operation before outputting it.
Just an idea.
Lyal Collins
financial transactions, termed a MAC
"signatures"are 4-8 bytes, key size is 8-16 bytes, and DES or other
symmetric algorithm.
If Smartcard is too costly, just do it in software, if the risks justify the
tampering or related potential exposures.
Lyal
Michael Amling
>>How come you only need the same security as RSA-512, in that case?
>>The first public 512-bit factorization was completed nearly four years
>>ago; these days it doesn't offer that much protection.
>
>
> The FAI specification specifies RSA-512.
> I Agree it could be better.
>
> Also the individualt Private keys signed by the public key makes a lot
> of sense, but then I've got to include both the public key,
> the key signature and the actual data signature in the verification
> data block. Still do able....
> Removing all formating and excess stuff....
> Individual public key 1024,
> Signature of key 1024
> Signature of digest 1024
> This is 384 bytes a fair bit of data.
Why would you want to store a copy of the signature on the device? If
you need the space, let the verifier look up or fetch the signature from
some database.
--Mike Amling
lurker
<http://phr...@NOSPAM.invalid> wrote:
Wouldn't the raw GPS signal be random at any given point? How would a
spoofer break into the connection? DOS attacks are allways a
possibility so the problem would be how to securely resynch.
Paul Rubin
> Wouldn't the raw GPS signal be random at any given point? How would a
> spoofer break into the connection? DOS attacks are allways a
> possibility so the problem would be how to securely resynch.
What connection? GPS is a radio signal and of course it's not random.
Spoofing GPS just means setting up a transmitter near your receiver,
so the attacker's signal is stronger than the satellite signal, so the
receiver hears what the attacker sends instead of what the satellite
sends. The attacker can then transmit signals that tell the receiver
that it's in Bolivia, or New York, or wherever it wants.
Military GPS uses the encrypted Y code to prevent this kind of
spoofing. However using it requires a secret key in the receiver.
Civilian receivers have no anti-spoofing protection.
lurker
<http://phr...@NOSPAM.invalid> wrote:
>n...@nospam.org (lurker) writes:
>> Wouldn't the raw GPS signal be random at any given point? How would a
>> spoofer break into the connection? DOS attacks are allways a
>> possibility so the problem would be how to securely resynch.
>
>What connection? GPS is a radio signal and of course it's not random.
>
I thought the satellites were more dificult to track and that the raw
signal was random. I wrote a little GW basic program a while back to
predict satellite orbits and I kept getting random results. Probably
just a truncated receiving field in my program. I guess I will have
to think about this a little more because I still can't figure out a
way to break the system considering the speeds involved with the
satellite.
Paul Rubin
> I thought the satellites were more dificult to track and that the raw
> signal was random.
What are you talking about? If it was random, it wouldn't carry any
information and your receiver might as well not listen to it. That it
carries an interesting signal at all means it's not random.
> I wrote a little GW basic program a while back to predict satellite
> orbits and I kept getting random results. Probably just a truncated
> receiving field in my program. I guess I will have to think about
> this a little more because I still can't figure out a way to break
> the system considering the speeds involved with the satellite.
You can buy GPS test equipment off the shelf that simulates the
satellite signal. You don't have to figure out anything except how to
pay for it and read the instructions to get it going.