ECDSA with naive message passing [Cryptography]

Prev: What could WYLBNIMGTHAD possibly mean?
Next: Converting byte[] to ASN1 stream fails - reads until byte 22

From: Yehudidedum on 27 Jul 2010 12:03

I do not know much about cryptography so any help is
very much appreciated.

If I wanted to broadcast a series of message of 4 bytes
that was incrementing each second.
'0x4C4EF473', '0x4C4EF474' etc.
I have no need what so ever to hide the contents
of the message I only want to be able to tell who
sent it.
The problem is that I only have perhaps 192 bits of
possible bandwidth to carry the entire data, both
message and signature.

I could use ECDSA(192) with a "message recovery scheme.
If I use a very naive approach for this, say. Instead
of passing in a 384 bit hash of a message I pass in
384 bits of data containing a validation marker, some
random padding, and the message.
Marker = 0x12345678987654320000 80 bits.
Message = '4C4E F473'. 32 bits

So once every second I am producing something that
when decoded using the public key gives:
'1234567898765432000XXXX.. ..XXXX4C4E F473'
(XXXXXX indicates random padding)

My question is using this approach am I making it easy to
(a) Discover the private key
(b) Easily spoof a message

Again, many thanks for even reading this far.
Yehudi
Boss: Yehudi, why ruin the DSA security?
....Was it ignorance or apathy?
Yehudi: I dont know and I dont care

From: Tom St Denis on 27 Jul 2010 12:20

On Jul 27, 12:03 pm, Yehudidedum <pete.mce...(a)metastate.co.uk> wrote:
> I do not know much about cryptography so any help is
> very much appreciated.
>
> If I wanted to broadcast a series of message of 4 bytes
> that was incrementing each second.
> '0x4C4EF473', '0x4C4EF474' etc.
> I have no need what so ever to hide the contents
> of the message I only want to be able to tell who
> sent it.
> The problem is that I only have perhaps 192 bits of
> possible bandwidth to carry the entire data, both
> message and signature.
>
> I could use ECDSA(192) with a "message recovery scheme.
> If I use a very naive approach for this, say. Instead
> of passing in a 384 bit hash of a message I pass in
> 384 bits of data containing a validation marker, some
> random padding, and the message.
> Marker = 0x12345678987654320000 80 bits.
> Message = '4C4E F473'. 32 bits
>
> So once every second I am producing something that
> when decoded using the public key gives:
> '1234567898765432000XXXX.. ..XXXX4C4E F473'
> (XXXXXX indicates random padding)
>
> My question is using this approach am I making it easy to
> (a) Discover the private key
> (b) Easily spoof a message

Well an EC-DSA signature will be bigger than 192-bits. The smallest
you could get by [with standards] is around 48 bytes or so (163-bit
curve).

You'll have to use another scheme if you only have so many bits, like
maybe a signature in batches, e.g. sign the value (counter & ~0xF)
then over 16 messages you spread out your 48 byte signature (e.g. 3
bytes per counter). Then every 16 messages people can verify that
the last 16 messages came from someone they know. If you can fit
closer to 192-bits [24 bytes] you can get away with spreading it over
4 messages by signing (counter & ~0x3) thus reducing your window of
vulnerability.

Of course I assume you have some form of replay protection as well?

From: Ilmari Karonen on 27 Jul 2010 12:42

On 2010-07-27, Yehudidedum <pete.mcevoy(a)metastate.co.uk> wrote:
> I do not know much about cryptography so any help is
> very much appreciated.
>
> If I wanted to broadcast a series of message of 4 bytes
> that was incrementing each second.
> '0x4C4EF473', '0x4C4EF474' etc.
> I have no need what so ever to hide the contents
> of the message ? I only want to be able to tell who
> sent it.

Is this for a time synchronization protocol or something? That's the
only reason I can think of for wanting to broadcast a signed stream of
linearly increasing numbers.

> The problem is that I only have perhaps 192 bits of
> possible bandwidth to carry the entire data, both
> message and signature.

Tom's suggestion of splitting the signature over multiple messages
ought to work, with the obvious limitation of not allowing immediate
verification. However, have you considered simply trading off message
frequency for size? Do you really _need_ to send messages every
second, or would, say, 10 second intervals be feasible?

(Also, if this is for a time synchronization protocol, I assume you've
already consider all the various attack scenarios a signature won't
protect against. Naive replay attacks are, of course, easy to guard
against, since your messages already have (and indeed consist solely
of) a sequence number, but a suitably positioned attacker might also,
for example, be able to cause messages to be delayed or dropped, or
flood your receivers with bogus messages.)

--
Ilmari Karonen
To reply by e-mail, please replace ".invalid" with ".net" in address.

From: jbriggs444 on 27 Jul 2010 12:59

From: Yehudidedum on 27 Jul 2010 14:32

On Jul 27, 5:20 pm, Tom St Denis <t...(a)iahu.ca> wrote:
> On Jul 27, 12:03 pm, Yehudidedum <pete.mce...(a)metastate.co.uk> wrote:
>
>
>
> > I do not know much about cryptography so any help is
> > very much appreciated.
>
> > If I wanted to broadcast a series of message of 4 bytes
> > that was incrementing each second.
> > '0x4C4EF473', '0x4C4EF474' etc.
> > I have no need what so ever to hide the contents
> > of the message I only want to be able to tell who
> > sent it.
> > The problem is that I only have perhaps 192 bits of
> > possible bandwidth to carry the entire data, both
> > message and signature.
>
> > I could use ECDSA(192) with a "message recovery scheme.
> > If I use a very naive approach for this, say. Instead
> > of passing in a 384 bit hash of a message I pass in
> > 384 bits of data containing a validation marker, some
> > random padding, and the message.
> > Marker = 0x12345678987654320000 80 bits.
> > Message = '4C4E F473'. 32 bits
>
> > So once every second I am producing something that
> > when decoded using the public key gives:
> > '1234567898765432000XXXX.. ..XXXX4C4E F473'
> > (XXXXXX indicates random padding)
>
> > My question is using this approach am I making it easy to
> > (a) Discover the private key
> > (b) Easily spoof a message
>
> Well an EC-DSA signature will be bigger than 192-bits. The smallest
> you could get by [with standards] is around 48 bytes or so (163-bit
> curve).
>
> You'll have to use another scheme if you only have so many bits, like
> maybe a signature in batches, e.g. sign the value (counter & ~0xF)
> then over 16 messages you spread out your 48 byte signature (e.g. 3
> bytes per counter). Then every 16 messages people can verify that
> the last 16 messages came from someone they know. If you can fit
> closer to 192-bits [24 bytes] you can get away with spreading it over
> 4 messages by signing (counter & ~0x3) thus reducing your window of
> vulnerability.
>
> Of course I assume you have some form of replay protection as well?

Many thanks again, and Oops, like the great prophet Britney
Spears, I've done it again, I have incorrectly stated the available
bit size
for the message and sign. I had meant to put 384 or very slightly
above.

Really, I was most worried about generating many, many thousands of
messages that all had a known top set of bits, ie, the marker.
I wondered if this was perhaps a big aide when trying to deduce the
private
key, or finding spoofs.

Most message recovery schemes I have seen have complicated
mapping functions. I thought thiat this was probably implying
that a very simple scheme was very dangerous.

Again, thanks to Tom and to the others who have replied,
Yehudi

| Next | Last
Pages: 1 2
Prev: What could WYLBNIMGTHAD possibly mean?
Next: Converting byte[] to ASN1 stream fails - reads until byte 22