From: Yehudidedum on
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 don’t know and I don’t care”


From: Tom St Denis on
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
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
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.

Eh?

That's a pretty tight syntax constraint on your message
space. You can control the starting number and
the ending number and nothing else. All the remaining
data is uniquely determined by the 4 byte starting
value -- each 4 byte value is one higher than the
previous.

There are only 2^64 - 2^32 + 1 such messages available
and the +1 is only usable if you count the empty
message.

How are you planning to fit 192 bytes of signature into
a message that contains less than 64 bits of information?

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

How did you arive at this figure? And having arrived
at it, why would the coding scheme that supposedly
imposes the 192 bit constraint be relevant?
From: Yehudidedum on
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