Encrypting control channel

[Don Y]

Hi,

[first post, here, so be gentle :>]

I'm designing a multimedia "distribution" system.
The goal, here, is not to protect *content* but,
rather, exploit packet switching technologies to
economically distribute ("broadcast") audio and
video over large distances without noticeable
(audio/video) signal degradation.

Imagine our house/concert hall/amphitheater as
a "multimedia device" with components and wiring
"inside". (e.g., a BoomBox from The Land of the
Giants [apologies for cultural reference]).

In that "boombox", you would just run wires from
signal source (e.g., amplifier output) to signal
destination (e.g., speakers, "line out" jacks, etc.).
YOU WOULDN'T DO ANYTHING OUT-OF-THE-ORDINARY TO THE
SIGNAL -- what's the point?

Now, again thinking in terms of The Land of the Giants,
imagine there are entities (the "little people" in
the aforementioned scenario) that can infest that
giant boombox.

You (probably) don't care if they listen/watch the
program material you are distributing in that box.
After all, they can poke their little heads *outside*
the box and enjoy it just like any of the intended
audience.

*But*, you'd be pretty annoyed if they could replace
or interfere with the production of that material!
E.g., substituting some other source material...
or, messing with the "volume control", etc.

So, how to protect the control (in the general sense
of the word) so that, at best, the little critters
can *interrupt* its production (you can never prevent
them from cutting wires!) but never hijack the
system for their own, devious purposes.

[sorry for the silly analogy but it hits most of the
issues]

I can embed secrets in the devices on each end of the
process. Though the design of those devices itself
is entirely open (the resulting devices will be released
as open source hardware/software so *anyone* could
design something to coexist -- peacefully or otherwise - on
the same wire.

Since the program material itself does not need to be
protected (hidden), I figure a fast, secure hash could
be used to reject "forged" materials presented to these
devices. The devices themselves have some smarts to
protect against certain anomalies in the signals (akin
to protecting the output stage of an amplifier in that
oversized boombox from short circuits, etc.)

There are several levels of control that need to be
present (e.g., firmware updates, configuration management,
signal processing, etc.) that I would like to address with
a common mechanisms -- despite their different levels of
severity (e.g., altering the firmware in the device is
more critical than preventing the "volume"/"contrast"/etc.
of the source material).

Note that the case of something ("little people") interfering
with the production of that pogram material is handled by
the user ferreting out the interloper and eradicating it.
(i.e., its not the system's job to identify and/or isolate
the interloper; merely to report that it has encountered
"faults" that it has protected itself against -- and the
user must identify if something has "infested" his system).

[I hope I've covered every aspect. If not, feel free to ask]

Thanks!
--don

[Robert Wessel]

I think you're basically looking for the ability to sign the
individual objects in question. That's a common requirement, and
usually involves a cryptographically secure hash of the object, and
then signing that hash with the private key of a public key encryption
scheme. The receiver decrypts the hash with the public key, and
compares it to a recomputation of the hash of the object.

Just a hash alone doesn't do it, that can easily be recomputed, but a
good (cryptographically secure) hash is a vital part. A poor hash
allows the construction of a forged document that generates the same
hash, which would obviously pass the signature test.

Digital signatures have a lot of literature, and the overview at
Wikipedia is pretty good. Basically there are three things that are
usually considered functions of digital signatures: authentication
(prove who the sender is), integrity (prove the object has not been
altered), and non-repudiation (and prove that someone sent an object).
Only the first two appear applicable to your application.

In principal, this can be as simple as computing a SHA-256 hash of the
object, and encrypting that 256-bit hash with a private RSA key, and
transmitting that with the object. The receiver uses the public RSA
key to decrypt the hash, and compares that with a new SHA-256 of the
object. So long as the private key remains secret, that works. There
are a bunch of details, however. Obviously key distribution is an
issue, as well as protecting against replay attacks, not to mention
key generation, sources of entropy for nonces, and a host of other
issues.

But as a general comment, this is tricky stuff to get right, and many
efforts have met disaster on the many details. The problem is that
utterly crap efforts are largely indistinguishable from good work,
until the former fall apart in the field. The use of well tested
tools from folks who know the subject is highly recommended. At the
very least carefully follow one of the well thought out digital
signature schemes - people have worked long and hard on those. You
could do a lot worse than starting with DSA.

[Greg Rose]

Mostly good advice, except:

In article <k9cpg71lujds3euc2...@4ax.com>,

Robert Wessel <robert...@yahoo.com> wrote:
>In principal, this can be as simple as computing a SHA-256 hash of the
>object, and encrypting that 256-bit hash with a private RSA key, and
>transmitting that with the object. The receiver uses the public RSA
>key to decrypt the hash, and compares that with a new SHA-256 of the
>object. So long as the private key remains secret, that works.

You don't "encrypt with the private key". You
*sign* the hash. The recipient *verifies* the
signature. Even in RSA, the only system where the
mathematics looks like it works either way, the
requirements for signing and encryption are very
different.

So, consider this just one of the ways that it's
hard to get this stuff right.

Greg.
--

[Christopher Head]

In addition to the good advice given by the prior posters (digital
signature schemes), I note that in your original message, you basically
say that the hardware at each end is fully controlled by you and you
can embed a shared secret into all devices if necessary.

In addition to digital signature schemes, I would urge you to look into
HMACs (Hashed Message Authentication Codes). These are basically the
symmetric-key equivalent to signature schemes: anyone who possesses the
secret key can both create and verify MACs, while anyone who does not
possess the key cannot do this. As long as you assume that both the
broadcaster and the receivers are safe from compromise, this is
perfectly adequate as an attacker trying to modify your data cannot
compute a proper MAC without the key (the same guarantee that a
signature scheme gives you). The difference is that an HMAC is
computationally much cheaper than most asymmetric digital signature
schemes: it consists of nothing more than applying a hash function
twice, whereas digital signature schemes use large-integer arithmetic.

Chris

[Robert Wessel]

True, although I was trying to give a specific example, and while
inartfully worded, in a simple case of using RSA to sign something, it
is an RSA encryption of the (signed) item being performed. That can
be the entire document (although that leaves an issue with integrity,
no to mention performance), or more commonly, of a hash of the
original object (which, if cryptographically, secure deals with the
integrity issue as well).

But as you point out, that's not true in general for digital signature
algorithms (just this the specific case).

Although as Christopher pointed out, encrypting with a symmetric
algorithm may be possible for the OP, which would be far less
expensive. But I'm not 100% clear on whether the OP is claiming he
can safely put the (same) secret key on all devices on the network.
Even then, he has some items (firmware updates), which may need more.

[Peter Gutmann]

Christopher Head <ch...@is.invalid> writes:

>In addition to the good advice given by the prior posters (digital
>signature schemes), I note that in your original message, you basically
>say that the hardware at each end is fully controlled by you and you
>can embed a shared secret into all devices if necessary.

>In addition to digital signature schemes, I would urge you to look into
>HMACs (Hashed Message Authentication Codes). These are basically the
>symmetric-key equivalent to signature schemes: anyone who possesses the
>secret key can both create and verify MACs, while anyone who does not
>possess the key cannot do this. As long as you assume that both the
>broadcaster and the receivers are safe from compromise, this is
>perfectly adequate as an attacker trying to modify your data cannot
>compute a proper MAC without the key (the same guarantee that a
>signature scheme gives you). The difference is that an HMAC is
>computationally much cheaper than most asymmetric digital signature
>schemes: it consists of nothing more than applying a hash function
>twice, whereas digital signature schemes use large-integer arithmetic.

It's not just the computational overhead, public-key crypto key management is
really, really hard to do for non-crypto-geeks, while shared-secret is
relatively straightforward.

Peter.

[Greg Rose]

In article <hl4qg7p2de1p9u0c7...@4ax.com>,

Sorry to belabor the point, but this isn't true,
even for RSA. The padding needs to be different, and
for digital signatures you *must* hash, or it's
possible to forge signatures on other messages.

>Although as Christopher pointed out, encrypting with a symmetric
>algorithm may be possible for the OP, which would be far less
>expensive. But I'm not 100% clear on whether the OP is claiming he
>can safely put the (same) secret key on all devices on the network.
>Even then, he has some items (firmware updates), which may need more.

Yes, I glossed over the part of his post where
symmetric MACs might have been applied.

Greg.

--

[Don Y]

Hi Robert,

On 1/10/2012 3:08 PM, Robert Wessel wrote:
> On Tue, 10 Jan 2012 14:24:22 -0700, Don Y<th...@isnotme.com> wrote:

[Land of Giants retrospective elided]

> I think you're basically looking for the ability to sign the
> individual objects in question.

Yes.

> That's a common requirement, and
> usually involves a cryptographically secure hash of the object, and
> then signing that hash with the private key of a public key encryption
> scheme. The receiver decrypts the hash with the public key, and
> compares it to a recomputation of the hash of the object.

But why do I have to go the PK route? If I have a true "secret",
cant that, itself, be reliably used?

> Just a hash alone doesn't do it, that can easily be recomputed, but a
> good (cryptographically secure) hash is a vital part. A poor hash
> allows the construction of a forged document that generates the same
> hash, which would obviously pass the signature test.

Yes.

> Digital signatures have a lot of literature, and the overview at
> Wikipedia is pretty good. Basically there are three things that are
> usually considered functions of digital signatures: authentication
> (prove who the sender is), integrity (prove the object has not been
> altered), and non-repudiation (and prove that someone sent an object).
> Only the first two appear applicable to your application.
>
> In principal, this can be as simple as computing a SHA-256 hash of the
> object, and encrypting that 256-bit hash with a private RSA key, and
> transmitting that with the object. The receiver uses the public RSA
> key to decrypt the hash, and compares that with a new SHA-256 of the
> object. So long as the private key remains secret, that works. There
> are a bunch of details, however. Obviously key distribution is an
> issue, as well as protecting against replay attacks, not to mention
> key generation, sources of entropy for nonces, and a host of other
> issues.

Why can't I, for (naive) example prepend the "secret" to the hashed
data knowing that the sender did likewise?

> But as a general comment, this is tricky stuff to get right, and many

<grin> Hence the reason I ask! :> (I've already anticipated some
attacks -- which I will clarify once the discussion settles on an
approach)

[Don Y]

Hi Christopher,

On 1/10/2012 9:34 PM, Christopher Head wrote:
> In addition to the good advice given by the prior posters (digital
> signature schemes), I note that in your original message, you basically
> say that the hardware at each end is fully controlled by you and you
> can embed a shared secret into all devices if necessary.

Exactly. This can be done at manufacture/deployment. It is impractical
(IMHO) to protect against a physical attack where you don't truly have
physical security (talk to the folks in the gaming industry :> ).
If an attacker wanted to screw with such a system, it is much simpler
to arrange for a DoS attack on it.

Witness the extent to which the entertainment industry attempts to
protect their "content" and how routinely those attempts are
thwarted.

> In addition to digital signature schemes, I would urge you to look into
> HMACs (Hashed Message Authentication Codes). These are basically the
> symmetric-key equivalent to signature schemes: anyone who possesses the
> secret key can both create and verify MACs, while anyone who does not
> possess the key cannot do this. As long as you assume that both the
> broadcaster and the receivers are safe from compromise, this is
> perfectly adequate as an attacker trying to modify your data cannot
> compute a proper MAC without the key (the same guarantee that a
> signature scheme gives you).

This relies on NOT being able to generate "bogus" data that hashes
the same as "valid" data. I seem to recall a paper talking about
ways to create just such bogus data (recently?)

It would also have to be amended to guard against replay attacks (?)

> The difference is that an HMAC is
> computationally much cheaper than most asymmetric digital signature
> schemes: it consists of nothing more than applying a hash function
> twice, whereas digital signature schemes use large-integer arithmetic.

Exactly what I want to avoid. There is a fair amount of control
traffic passed between nodes. Much of it has significant real-time
constraints (e.g., "I missed packet #28. Could you please resend
it to me?"). So, any verification algorithm has to be able to
run within that RT context. (and, of course, I am trying to
drive the cost/complexity of the hardware through the floor...)

[Don Y]

Hi Robert,

On 1/10/2012 9:53 PM, Robert Wessel wrote:
> On Tue, 10 Jan 2012 22:41:55 +0000 (UTC), g...@nope.ucsd.edu (Greg
> Rose) wrote:
>
>> Mostly good advice, except:
>>
>> In article<k9cpg71lujds3euc2...@4ax.com>,
>> Robert Wessel<robert...@yahoo.com> wrote:
>>> In principal, this can be as simple as computing a SHA-256 hash of the
>>> object, and encrypting that 256-bit hash with a private RSA key, and
>>> transmitting that with the object. The receiver uses the public RSA
>>> key to decrypt the hash, and compares that with a new SHA-256 of the
>>> object. So long as the private key remains secret, that works.
>>
>> You don't "encrypt with the private key". You
>> *sign* the hash. The recipient *verifies* the
>> signature. Even in RSA, the only system where the
>> mathematics looks like it works either way, the
>> requirements for signing and encryption are very
>> different.
>

> True, although I was trying to give a specific example, and while
> inartfully worded, in a simple case of using RSA to sign something, it
> is an RSA encryption of the (signed) item being performed. That can
> be the entire document (although that leaves an issue with integrity,
> no to mention performance), or more commonly, of a hash of the
> original object (which, if cryptographically, secure deals with the
> integrity issue as well).
>
> But as you point out, that's not true in general for digital signature
> algorithms (just this the specific case).
>
> Although as Christopher pointed out, encrypting with a symmetric
> algorithm may be possible for the OP, which would be far less
> expensive. But I'm not 100% clear on whether the OP is claiming he
> can safely put the (same) secret key on all devices on the network.

The *initial* key can be distributed reliably...

> Even then, he has some items (firmware updates), which may need more.

Exactly. Actually, there are several "other details" that threaten
any particular scheme. I hesitate to bring everything up at once
as it gets too hard to track different lines of argument -- "settle"
on one issue before tackling the next :-/

[kg]

Don Y <th...@isnotme.com> wrote:
>Why can't I, for (naive) example prepend the "secret" to the hashed
>data knowing that the sender did likewise?

Because that specific example is insecure, it could in this instance
allow an attacker to pad your commands with data of his own choice.

Use a proper MAC with your secret as a key instead.

--
kg

[Don Y]

On 1/11/2012 11:29 AM, kg wrote:
> Don Y<th...@isnotme.com> wrote:
>> Why can't I, for (naive) example prepend the "secret" to the hashed
>> data knowing that the sender did likewise?
>
> Because that specific example is insecure, it could in this instance
> allow an attacker to pad your commands with data of his own choice.

How? Anything "tacked onto the end" (padding) would need to NOT
alter the hash *and* fit into the same space as the original message.
(i.e., this devolves into being able to create an arbitrary packet
that hashes the same as a legitimate packet, doesn't it?)

[kg]

Look up "length extension attack".

--
kg

[Don Y]

On 1/11/2012 4:15 PM, kg wrote:
> Don Y<th...@isnotme.com> wrote:
>> On 1/11/2012 11:29 AM, kg wrote:
>>> Don Y<th...@isnotme.com> wrote:
>>>> Why can't I, for (naive) example prepend the "secret" to the hashed
>>>> data knowing that the sender did likewise?
>>>
>>> Because that specific example is insecure, it could in this instance
>>> allow an attacker to pad your commands with data of his own choice.
>>
>> How? Anything "tacked onto the end" (padding) would need to NOT
>> alter the hash *and* fit into the same space as the original message.

------------------------^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

>> (i.e., this devolves into being able to create an arbitrary packet
>> that hashes the same as a legitimate packet, doesn't it?)
>
> Look up "length extension attack".

Sorry, perhaps my comments (above) were unclear (or, Ive missed your
intent completely!).

The size of the message is IMPLICITLY known to sender and receiver.
(this isn't a general purpose system but, rather, one that exists
within rigidly defined operational and resource constraints).

"lengthening" the message immediately flags the message as invalid:
"Where the heck did all these extra octets come from???"

If the sender wants to send a "longer" message it becomes a succession
of (fixed length) messages each individually "protected".

So, if the sender only emits messages of that *fixed* size (note that
different messages might have different sizes but each message of
type "foo" consists of exactly foo.length octets), the attacker
has to be able to synthesize a message that looks like one of those.

[Christopher Head]

On Wed, 11 Jan 2012 11:18:15 -0700
Don Y <th...@isnotme.com> wrote:

[snip]

> This relies on NOT being able to generate "bogus" data that hashes
> the same as "valid" data. I seem to recall a paper talking about
> ways to create just such bogus data (recently?)

The attacks I've heard of most recently were against MD5, and SHA1 is
widely agreed to be on the edge of possibly seeing a break shortly.
Since this is a brand new deployment, you get to choose your hash
function; I'd go with something stronger like SHA256 or SHA512. Note
that this exact problem also exists when using an asymmetric digital
signature scheme, since they also use hashes.

> It would also have to be amended to guard against replay attacks (?)

Replay protection isn't inherently provided by either digital
signatures or HMACs, so you would need to make it a separate part of
the protocol. Quite trivially, a large counter (just go with 64 or 128
bits so you don't have to worry about overflow, if you can afford it in
bandwidth) attached to each packet will solve this; the sender starts
at zero and increments the counter for each packet while the recipients
refuse to accept a packet unless it has a sequence number greater than
any they've seen before (this also lets you notice if a packet was
dropped since there will be a sequence number hole; if you don't care
about that just ignore it).

As an aside, if any of your control messages are intended to be
directed at specific recipients, don't forget to include the identity of
the recipient in the HMAC to prevent an attacker from redirecting a
message.

> Exactly what I want to avoid. There is a fair amount of control
> traffic passed between nodes. Much of it has significant real-time
> constraints (e.g., "I missed packet #28. Could you please resend
> it to me?"). So, any verification algorithm has to be able to
> run within that RT context. (and, of course, I am trying to
> drive the cost/complexity of the hardware through the floor...)

An HMAC should be fine for fairly tight real-time work; as I said it
uses only two applications of a hash function, and in fact the second
application of the function doesn't even take the original message as
input, meaning it's of constant speed no matter how long the message is.

In another post, you said "Why can't I, for (naive) example prepend the
"secret" to the hashed data knowing that the sender did likewise?". An
HMAC does almost this, only it applies the hash function twice and uses
some small tweaks to the data in between applications which yield some
security improvements.

In particular, if H() is the hash function, K is the key, and M is the
message, sending H(K || M) is a bad idea because many hash functions
allow computing H(K || M || M') if H(K || M) is known; this allows an
attacker to append arbitrary data to your message without knowing the
key. The HMAC's construction prevents this.

If you tried to solve this by using H(M || K) instead, you would reduce
the difficulty of a brute-force attack against the key because an
attacker could precompute H(M); by putting the key first, the entire
message has to be rehashed for each attempt.

There are probably other reasons for doing this I'm not familiar with.
In any case, there's really no good reason not to use an HMAC; the
construction is set up so it can even be used inline in a streaming
system: computing an HMAC over a message requires only a single forward
pass over the message, along with a small amount of preprocessing
before the message starts and a small amount of postprocessing after it
ends.

Chris

[kg]

Don Y <th...@isnotme.com> wrote:
>The size of the message is IMPLICITLY known to sender and receiver.

Well, in certain restricted cases H(key, m) can be a good MAC. However,
it isn't very robust (what if the message format suddenly changes?)
and the cost of using a proper MAC is usually negligible.

Unless it is absolutely certain that you cannot afford a proper MAC, but
you can afford a hash with a prefixed key, I would go for a proper MAC.

--
kg

[Don Y]

On 1/12/2012 1:04 AM, kg wrote:
> Don Y<th...@isnotme.com> wrote:
>> The size of the message is IMPLICITLY known to sender and receiver.
>
> Well, in certain restricted cases H(key, m) can be a good MAC. However,
> it isn't very robust (what if the message format suddenly changes?)
> and the cost of using a proper MAC is usually negligible.

Understood. My comments were an attempt to clarify how the exploit
could (or couldn't) be applicable. Remember, the adversary *knows*
(or has a darn good feel for!) what is in most of the messages
that are set down the wire...

[Don Y]

Hi Chris,

On 1/11/2012 9:36 PM, Christopher Head wrote:
> On Wed, 11 Jan 2012 11:18:15 -0700
> Don Y<th...@isnotme.com> wrote:
>
>> This relies on NOT being able to generate "bogus" data that hashes
>> the same as "valid" data. I seem to recall a paper talking about
>> ways to create just such bogus data (recently?)
>
> The attacks I've heard of most recently were against MD5, and SHA1 is
> widely agreed to be on the edge of possibly seeing a break shortly.
> Since this is a brand new deployment, you get to choose your hash
> function; I'd go with something stronger like SHA256 or SHA512. Note

Ouch! <frown> The problems with longer/"bigger" hashes are:
- they start to eat up a lot of communications bandwidth
(I strive to keep packets small as that gives the clients the
most flexibility in utilizing them)
- they start to rival the signal processing costs

> that this exact problem also exists when using an asymmetric digital
> signature scheme, since they also use hashes.
>
>> It would also have to be amended to guard against replay attacks (?)
>
> Replay protection isn't inherently provided by either digital
> signatures or HMACs, so you would need to make it a separate part of
> the protocol. Quite trivially, a large counter (just go with 64 or 128
> bits so you don't have to worry about overflow, if you can afford it in
> bandwidth) attached to each packet will solve this; the sender starts
> at zero and increments the counter for each packet while the recipients
> refuse to accept a packet unless it has a sequence number greater than
> any they've seen before (this also lets you notice if a packet was
> dropped since there will be a sequence number hole; if you don't care
> about that just ignore it).

I'd have to tweek this since packets *can* arrive out of order (within
contraints) in the normal course of operation. And, you'd also have
to consider the case of re-requesting a "lost packet" (what counter
value does it merit?).

Also, you would have to maintain such a "counter" for each,
(sender,receiver), right? (though, presumably, one per *sender*
could suffice if you had other mechanisms to track missing packets)

> As an aside, if any of your control messages are intended to be
> directed at specific recipients, don't forget to include the identity of
> the recipient in the HMAC to prevent an attacker from redirecting a
> message.

Ah, good point! Of course, that identification can be cheap -- a
"small integer" that is specified at session start ("You are number 3")

>> Exactly what I want to avoid. There is a fair amount of control
>> traffic passed between nodes. Much of it has significant real-time
>> constraints (e.g., "I missed packet #28. Could you please resend
>> it to me?"). So, any verification algorithm has to be able to
>> run within that RT context. (and, of course, I am trying to
>> drive the cost/complexity of the hardware through the floor...)
>
> An HMAC should be fine for fairly tight real-time work; as I said it
> uses only two applications of a hash function, and in fact the second
> application of the function doesn't even take the original message as
> input, meaning it's of constant speed no matter how long the message is.

Understood. Note that I would also have to apply this (or something
similar) to the actual *data* stream, as well, to ensure *that* wasnt
being replaced (i.e., instead of listening to Bach, you find yourself
listening to Dr Demento).

> In another post, you said "Why can't I, for (naive) example prepend the
> "secret" to the hashed data knowing that the sender did likewise?". An
> HMAC does almost this, only it applies the hash function twice and uses
> some small tweaks to the data in between applications which yield some
> security improvements.
>
> In particular, if H() is the hash function, K is the key, and M is the
> message, sending H(K || M) is a bad idea because many hash functions
> allow computing H(K || M || M') if H(K || M) is known; this allows an
> attacker to append arbitrary data to your message without knowing the
> key. The HMAC's construction prevents this.

Yes, but (as I replied elsewhere), len(K || M) != len(K || M || M').
In the current case, sender and recipient both *know* how large each
message should be. Seeing something "extra" tacked on the end would
be indicative of a system failure: "Can't Happen".

Even variable length messages (length not known a priori) could be
accommodated (?) if M included a "message length" field.

> If you tried to solve this by using H(M || K) instead, you would reduce
> the difficulty of a brute-force attack against the key because an
> attacker could precompute H(M); by putting the key first, the entire
> message has to be rehashed for each attempt.

Understood.

> There are probably other reasons for doing this I'm not familiar with.
> In any case, there's really no good reason not to use an HMAC; the
> construction is set up so it can even be used inline in a streaming
> system: computing an HMAC over a message requires only a single forward
> pass over the message, along with a small amount of preprocessing
> before the message starts and a small amount of postprocessing after it
> ends.

[apologies if I am late replying; my traditional mail/news machine is
still in pieces so Ive been living without my normal news feed for
about a month... maybe I'll get the machine rebuilt soon! :> ]

[Andrew Swallow]

Use the same counter value it was originally sent with. Also repeat
packets if they are not acknowledged within a reasonable amount of time.

> Also, you would have to maintain such a "counter" for each,
> (sender,receiver), right? (though, presumably, one per *sender*
> could suffice if you had other mechanisms to track missing packets)
>

That only needs a small amount of ram.

Andrew Swallow

[Don Y]

Hi Andrew,

On 1/12/2012 4:23 PM, Andrew Swallow wrote:
> On 12/01/2012 19:38, Don Y wrote:

[8<]

>>> that this exact problem also exists when using an asymmetric digital
>>> signature scheme, since they also use hashes.
>>>
>>>> It would also have to be amended to guard against replay attacks (?)
>>>
>>> Replay protection isn't inherently provided by either digital
>>> signatures or HMACs, so you would need to make it a separate part of
>>> the protocol. Quite trivially, a large counter (just go with 64 or 128
>>> bits so you don't have to worry about overflow, if you can afford it in
>>> bandwidth) attached to each packet will solve this; the sender starts
>>> at zero and increments the counter for each packet while the recipients
>>> refuse to accept a packet unless it has a sequence number greater than
>>> any they've seen before (this also lets you notice if a packet was
>>> dropped since there will be a sequence number hole; if you don't care
>>> about that just ignore it).
>>
>> I'd have to tweek this since packets *can* arrive out of order (within
>> contraints) in the normal course of operation. And, you'd also have
>> to consider the case of re-requesting a "lost packet" (what counter
>> value does it merit?).
>
> Use the same counter value it was originally sent with.

Which means the "counter value" (avoiding the use of the term
"sequence number") checking has to be done upstream of the
"replay prevention" logic.

> Also repeat
> packets if they are not acknowledged within a reasonable amount of time.

Packets are never acknolwedged. That adds lots of extra traffic.
Instead, you *assume* the packets get to their destinations
and *they* (i.e., the "detinations") react if they don't.

What's a "reasonable amount of time"? Only the particular destination
knows that, for sure (of course, you *could* centralize this information
but that increases the burden on the servers/senders and doesn't scale
well).

OTOH, a destination can more readily decide the chance of it being
able to succesfully rerequest a lost packet and alter (or, *begin*
altering) its behavior, accordingly.

>> Also, you would have to maintain such a "counter" for each,
>> (sender,receiver), right? (though, presumably, one per *sender*
>> could suffice if you had other mechanisms to track missing packets)
>
> That only needs a small amount of ram.

Yes -- for each counter. But, you need one for each *sender*
(which each "recipient" must track). If you don't want the
counters to wrap (replay), then they need to be wide (since
a session can be of indefinite length).

[Andrew Swallow]

In simple terms they are the same test. In a simple system you are
probably discarding packets after the missing packet, more sophisticated
systems can queue the packets.

>> Also repeat
>> packets if they are not acknowledged within a reasonable amount of time.
>
> Packets are never acknolwedged. That adds lots of extra traffic.
> Instead, you *assume* the packets get to their destinations
> and *they* (i.e., the "detinations") react if they don't.
>
> What's a "reasonable amount of time"? Only the particular destination
> knows that, for sure (of course, you *could* centralize this information
> but that increases the burden on the servers/senders and doesn't scale
> well).
>
> OTOH, a destination can more readily decide the chance of it being
> able to succesfully rerequest a lost packet and alter (or, *begin*
> altering) its behavior, accordingly.
>
>>> Also, you would have to maintain such a "counter" for each,
>>> (sender,receiver), right? (though, presumably, one per *sender*
>>> could suffice if you had other mechanisms to track missing packets)
>>
>> That only needs a small amount of ram.
>
> Yes -- for each counter. But, you need one for each *sender*
> (which each "recipient" must track). If you don't want the
> counters to wrap (replay), then they need to be wide (since
> a session can be of indefinite length).

The receiver can test for gaps but does not know if it has received the
last packet.

128 bits per subscriber, which is 16 bytes. For anything other than an
8051 microcontroller that is trivial. RAM is cheap theses days.

Andrew Swallow

[Don Y]

Hi Andrew,

No. They address different issues.

The "sequence number" of a packet determines its place in the
"source stream". I.e., the contents of packets bearing the
sequence numbers N-1, N, N+1 are "played"/"displayed" in
exactly that sequence. (similar arguments apply to the
sequence of "control messages")

The "counter value(s)" exist solely to prevent replay attacks.

> In a simple system you are
> probably discarding packets after the missing packet, more sophisticated
> systems can queue the packets.

I *never* drop a packet -- unless its deadline has passed
(stale data). If I receive 3, 8, 5, 7, 2... then I enqueue
them so that *when* they are supposed to be "played", they
are ready and waiting.

The senders' emission rates are syntonous with the receivers'
consumption rates -- data arrives at a client because (and *when*)
it needs that data (this isn't a desktop player/STB, etc. that
can buffer huge amounts of data and request whatever it might
*decide* it needs at a later time).

[look to the boombox analogy]

>>> Also repeat
>>> packets if they are not acknowledged within a reasonable amount of time.
>>
>> Packets are never acknolwedged. That adds lots of extra traffic.
>> Instead, you *assume* the packets get to their destinations
>> and *they* (i.e., the "detinations") react if they don't.
>>
>> What's a "reasonable amount of time"? Only the particular destination
>> knows that, for sure (of course, you *could* centralize this information
>> but that increases the burden on the servers/senders and doesn't scale
>> well).
>>
>> OTOH, a destination can more readily decide the chance of it being
>> able to succesfully rerequest a lost packet and alter (or, *begin*
>> altering) its behavior, accordingly.
>>
>>>> Also, you would have to maintain such a "counter" for each,
>>>> (sender,receiver), right? (though, presumably, one per *sender*
>>>> could suffice if you had other mechanisms to track missing packets)
>>>
>>> That only needs a small amount of ram.
>>
>> Yes -- for each counter. But, you need one for each *sender*
>> (which each "recipient" must track). If you don't want the
>> counters to wrap (replay), then they need to be wide (since
>> a session can be of indefinite length).
>
> The receiver can test for gaps but does not know if it has received the
> last packet.

There is never a "last packet" (as in last = final). The data
stream continues as long as the device is powered -- it just
is encoded as "silence" when no audio/video is intended to
be played/displayed (assuming the device isn't powered down
at that time).

Each receiver can examine the "seqence numbers" of the (validated)
packets that it has accumulated at any given time. From this, it
knows when -- and for how long into the immediate future -- it
can play/display the "source content". And, what it can *expect*
to arrive (asuming no problems) hereafter. If it's inspection
of its current state and expected future state leads it to
suspect that it might NOT have a piece of that source material,
it can:
- request it (from anyone who can provide it!)
- begin taking measures to gracefully degrade performance
to minimze the impact of the *apparently* upcoming dropout.

> 128 bits per subscriber, which is 16 bytes. For anything other than an
> 8051 microcontroller that is trivial. RAM is cheap theses days.

You're thinking of small numbers of clients and servers.
If the numbers are small, there is no need for so elaborate
a distribution system!

Imagine dozens of "source providers" and *hundreds* of clients.
Every "communication pair" -- i.e., (sender,receiver) -- that
is active (or POTENTIALLY active) would need such a counter
in each receiver (I think you can lump all of the "receivers"
for a particular sender into a single "sender-side" counter).

E.g., if a particular client subscribes to two source streams
provided by two different servers, then it must maintain a
"replay counter" for each of those "connections" -- in
addition to the two "sequence counters" for those two *streams*.

If control is provided by another server, then that adds
a third replay counter that th client must track.

Additionally, any peer relations that it relies upon would
require counters -- one for each peer. (I *think* you
only need to have a "receiver" counter for each such
relationship... I suspect a single "sender" counter could
be shared among all OUTBOUND connections from the client).

Without the security burdens, I currently can accommodate
an unlimited number of peers -- I don't have to maintain
*any* state for these connections as I can consider them
"temporary"/transitory (i.e., I don't even have to
track them in ARP cache). All I have to do is make sure
my "sequence count" can't wrap in the TTL of a packet on
the wire...

If I have to carry lots of state for each potential connection,
then I need to develop a protocol whereby each client can
establish -- and register -- the peer relationships that
it will track going forward. And, a mechanism for reseeding
those relationships over time (.e., when clients are powered
up/down or move to alternate "source subscriptions")

[Andrew Swallow]

The same counter will do both jobs. If you get N 3 times you keep the
first and throw away the other two.

>> In a simple system you are
>> probably discarding packets after the missing packet, more sophisticated
>> systems can queue the packets.
>
> I *never* drop a packet -- unless its deadline has passed
> (stale data). If I receive 3, 8, 5, 7, 2... then I enqueue
> them so that *when* they are supposed to be "played", they
> are ready and waiting.
>

You drop on power down. Every body does. Recovery by requesting a
retransmission.

For a communications network hundreds is small.

> Every "communication pair" -- i.e., (sender,receiver) -- that
> is active (or POTENTIALLY active) would need such a counter
> in each receiver (I think you can lump all of the "receivers"
> for a particular sender into a single "sender-side" counter).
>

Only if it is a multi-drop (like a radio broadcast) and everybody
listens to everything.

> E.g., if a particular client subscribes to two source streams
> provided by two different servers, then it must maintain a
> "replay counter" for each of those "connections" -- in
> addition to the two "sequence counters" for those two *streams*.
>

Correct.

> If control is provided by another server, then that adds
> a third replay counter that th client must track.
>
> Additionally, any peer relations that it relies upon would
> require counters -- one for each peer. (I *think* you
> only need to have a "receiver" counter for each such
> relationship... I suspect a single "sender" counter could
> be shared among all OUTBOUND connections from the client).
>

See above

> Without the security burdens, I currently can accommodate
> an unlimited number of peers -- I don't have to maintain
> *any* state for these connections as I can consider them
> "temporary"/transitory (i.e., I don't even have to
> track them in ARP cache). All I have to do is make sure
> my "sequence count" can't wrap in the TTL of a packet on
> the wire...
>
> If I have to carry lots of state for each potential connection,
> then I need to develop a protocol whereby each client can
> establish -- and register -- the peer relationships that
> it will track going forward. And, a mechanism for reseeding
> those relationships over time (.e., when clients are powered
> up/down or move to alternate "source subscriptions")

This depends on the level of reliability your network needs. Does it
matter to your clients that they get an entire song?

Andrew Swallow

[Don Y]

Hi Andrew,

>>>>>> I'd have to tweek this since packets *can* arrive out of order
>>>>>> (within
>>>>>> contraints) in the normal course of operation. And, you'd also have
>>>>>> to consider the case of re-requesting a "lost packet" (what counter
>>>>>> value does it merit?).
>>>>>
>>>>> Use the same counter value it was originally sent with.
>>>>
>>>> Which means the "counter value" (avoiding the use of the term
>>>> "sequence number") checking has to be done upstream of the
>>>> "replay prevention" logic.
>>>
>>> In simple terms they are the same test.
>>
>> No. They address different issues.
>>
>> The "sequence number" of a packet determines its place in the
>> "source stream". I.e., the contents of packets bearing the
>> sequence numbers N-1, N, N+1 are "played"/"displayed" in
>> exactly that sequence. (similar arguments apply to the
>> sequence of "control messages")
>>
>> The "counter value(s)" exist solely to prevent replay attacks.
>
> The same counter will do both jobs. If you get N 3 times you keep the
> first and throw away the other two.

Server wants to send a control message to that client.
What value does it use for "sequence number" (which you
claim shall be equivalent to "replay counter value")?
Remember, N-1, N and N+1 are already spoken for...

Then, send a control message to some *other* client...

And, eventually get around to emitting packet N+2...

Client #2 never sees the control message that was
directed to Client #1. So, it doesn't know that
the value you chose for the "sequence counter"
was NOT related to the actual sequencing of the
source content. *It* thinks it has lost a packet!
(because you have opted to hijack the "sequence
number" functionality for "replay prevention" -- of
ALL MESSAGES from the server!)

>>> In a simple system you are
>>> probably discarding packets after the missing packet, more sophisticated
>>> systems can queue the packets.
>>
>> I *never* drop a packet -- unless its deadline has passed
>> (stale data). If I receive 3, 8, 5, 7, 2... then I enqueue
>> them so that *when* they are supposed to be "played", they
>> are ready and waiting.
>
> You drop on power down. Every body does. Recovery by requesting a
> retransmission.

When a client is off, it doesn't exist. Powering up can't
be as simple as requesting retransmission because a
rogue can replay a stale packet and you wouldn't KNOW
that it wasn't "current".

I.e., powering up has to be a controlled protocol
before a client joins the "mesh".

Yup. So how many should I be able to track? Remember, this
isn't a PC. It's an appliance. Limited resources. Low
cost (e.g., the audio client is ~2 cu in -- CPU, network interface,
power supply, D/AC, audio amplifier, memory, etc. -- and costs
less than $20). I don't have "surplus" horsepower, memory,
etc. E.g., 100KB of RAM for *everything* -- the RTOS, process
control blocks, pushdown stacks, CODEC, control system, error
handling, decoding buffers, communications system, signal
processing, etc.

Should I set aside 2KB of that *just* for "replay counters"?
1KB? 3KB? Will "16 bytes" be *all* that is required to
track the state of a "communication path"? Or, will it
also need to record an associated unicast/multicast address?
Or "client ID"?

I.e., if I have to number messages, then I need to be able to
control the number of nodes with which I must interact. This
means another protocol (and the resources to implement it).
My current implementation doesn't have that "problem" (but
is insecure/vulnerable)

>> Every "communication pair" -- i.e., (sender,receiver) -- that
>> is active (or POTENTIALLY active) would need such a counter
>> in each receiver (I think you can lump all of the "receivers"
>> for a particular sender into a single "sender-side" counter).
>
> Only if it is a multi-drop (like a radio broadcast) and everybody
> listens to everything.

The server(s) broadcast source content. Clients pick the packets
associated with whichever source "channels" they want (based on what
they have previously been *told* to want! -- from control messages)
and keep track of what they *need* to satisfy their deadlines.
If they think they have missed a packet, they request it (from
a peer since requesting from the server would scale poorly). If
they think a packet that they need wont arrive in time, they
begin planning for its absence (so there are no abrupt
discontinuities in "playback")

Since all of the clients (plus the servers) represent a single
cooperating "system", they are constantly talking to each other
(exchanging performance statistics, synchronizing clocks,
rerequesting dropped/corrupt packets, etc)

Having all of this intercommunication be BROADCAST would
quickly swamp the network. So exchanges between peers
are typically unicast (though some of the discovery
protocols use multicast/broadcast)

If client 1 and client 2 are to talk to each other, they
surely can't use the same "sequence counter" that the
server was using to talk to all of them -- since the
server could be changing it "as they speak".

Likewise, client 2 and client 3 can't use the counter
that client 1 and 32 are using.

>> E.g., if a particular client subscribes to two source streams
>> provided by two different servers, then it must maintain a
>> "replay counter" for each of those "connections" -- in
>> addition to the two "sequence counters" for those two *streams*.
>
> Correct.

And, by extension, to any (sender,receiver) pair -- any
communication path that could exist.

>> If control is provided by another server, then that adds
>> a third replay counter that th client must track.
>>
>> Additionally, any peer relations that it relies upon would
>> require counters -- one for each peer. (I *think* you
>> only need to have a "receiver" counter for each such
>> relationship... I suspect a single "sender" counter could
>> be shared among all OUTBOUND connections from the client).
>
> See above

See above. :>

>> Without the security burdens, I currently can accommodate
>> an unlimited number of peers -- I don't have to maintain
>> *any* state for these connections as I can consider them
>> "temporary"/transitory (i.e., I don't even have to
>> track them in ARP cache). All I have to do is make sure
>> my "sequence count" can't wrap in the TTL of a packet on
>> the wire...
>>
>> If I have to carry lots of state for each potential connection,
>> then I need to develop a protocol whereby each client can
>> establish -- and register -- the peer relationships that
>> it will track going forward. And, a mechanism for reseeding
>> those relationships over time (.e., when clients are powered
>> up/down or move to alternate "source subscriptions")
>
> This depends on the level of reliability your network needs. Does it
> matter to your clients that they get an entire song?

Does it matter if the people in YOUR part of the building hear
the evacuation announcement?

[Christopher Head]

On Thu, 12 Jan 2012 12:38:33 -0700
Don Y <th...@isnotme.com> wrote:

> Ouch! <frown> The problems with longer/"bigger" hashes are:
> - they start to eat up a lot of communications bandwidth
> (I strive to keep packets small as that gives the clients the
> most flexibility in utilizing them)
> - they start to rival the signal processing costs

If bandwidth starts to become a problem due to large hashes, you could
consider instead using CBC-MAC mode. This is a mode of operation of a
block cipher which produces a message authentication code as output
rather than actually encrypting the data. The message authentication
code is the same size as the block size of the cipher, so that's only
128 bits in the case of AES. It's also possible to truncate the output
to an even smaller number of bits; IEEE802.15.4 does this though I'm
not sure if there are any non-obvious security implications (beyond the
simple reduced resistance to brute force).

I'm not sure how processing speed would compare to hashing, as both
hash algorithms and block ciphers are fairly complicated beasts. That
said, AES is pretty fast and it's also possible to get hardware
implementations which would burn through messages (there are also
hardware implementations of hash functions; as always, check what's
available and do what's best for your application).

Never use the same key for CBC-MAC authentication and CBC encryption.
If you want to use the same key for authentication and encryption, use
something like CCM (Counter with CBC-MAC), which is OK as long as the
CBC-MAC and CTR initialization vectors are chosen carefully. You didn't
mention needing to encrypt your messages here, so this probably doesn't
matter to you.

Chris

[Andrew Swallow]

If you only have one or two broadcasts going on at a time then the
server and the clients only need to remember a couple of broadcast
sequence numbers. They only need unicast sequence numbers for the
clients_and_servers they talk to.

The main source may not know that many of the clients exist. The network
can be split in areas, each area server being responsible for the
retransmissions in that area. In a big system there could be several
layers of servers.

Each retransmission server will have to keep copies of the packets it
retransmits.

> Since all of the clients (plus the servers) represent a single
> cooperating "system", they are constantly talking to each other
> (exchanging performance statistics, synchronizing clocks,
> rerequesting dropped/corrupt packets, etc)
>
> Having all of this intercommunication be BROADCAST would
> quickly swamp the network. So exchanges between peers
> are typically unicast (though some of the discovery
> protocols use multicast/broadcast)
>
> If client 1 and client 2 are to talk to each other, they
> surely can't use the same "sequence counter" that the
> server was using to talk to all of them -- since the
> server could be changing it "as they speak".
>
> Likewise, client 2 and client 3 can't use the counter
> that client 1 and 32 are using.
>

Your packet headers will have to include a field that says if the packet
is a broadcast packet or a unicast packet. Then the computer looks at
the record for that broadcast_ID or client_ID to find the requited
sequence number. There will also be transmission sequence numbers and
reception sequence numbers for unicast calls.

Then the server needs to tell the client that it has finished. Without
the end_of_message packet the client knows after a timeout that a packet
has been lost.

There have been packet switching and Store & Forward systems since the
Second World War I am surprised that one of these does not fit your
requirements. Or at least supply a good protocol.

Andrew Swallow

[Don Y]

Hi Christopher,

On 1/13/2012 1:31 AM, Christopher Head wrote:
> On Thu, 12 Jan 2012 12:38:33 -0700
> Don Y<th...@isnotme.com> wrote:
>
>> Ouch!<frown> The problems with longer/"bigger" hashes are:
>> - they start to eat up a lot of communications bandwidth
>> (I strive to keep packets small as that gives the clients the
>> most flexibility in utilizing them)
>> - they start to rival the signal processing costs
>
> If bandwidth starts to become a problem due to large hashes, you could

For any particular "comm path", the "source material" is
the biggest one penalized. 16, 32, 64 bytes for *just*
the "validation" can be a lot of overhead (there are
big efficiencies to be gained from keeping packets
small... but, the hash doesn't shrink with the shrinking
packet size :< )

> consider instead using CBC-MAC mode. This is a mode of operation of a
> block cipher which produces a message authentication code as output
> rather than actually encrypting the data. The message authentication
> code is the same size as the block size of the cipher, so that's only
> 128 bits in the case of AES. It's also possible to truncate the output
> to an even smaller number of bits; IEEE802.15.4 does this though I'm
> not sure if there are any non-obvious security implications (beyond the
> simple reduced resistance to brute force).

OK, I will look into it.

> I'm not sure how processing speed would compare to hashing, as both
> hash algorithms and block ciphers are fairly complicated beasts. That
> said, AES is pretty fast and it's also possible to get hardware
> implementations which would burn through messages (there are also
> hardware implementations of hash functions; as always, check what's
> available and do what's best for your application).

I'll prototype the algorithms and compile some (relative) performance
metrics.

> Never use the same key for CBC-MAC authentication and CBC encryption.

Why?

> If you want to use the same key for authentication and encryption, use
> something like CCM (Counter with CBC-MAC), which is OK as long as the
> CBC-MAC and CTR initialization vectors are chosen carefully. You didn't
> mention needing to encrypt your messages here, so this probably doesn't
> matter to you.

Correct. I am *not* interested in encryption -- and suspect it
would be too vulnerable (given that an attacker would have a
good idea what the plaintext of many of the messages was likely
to be). The "source material" can almost always be obtained by
a dedicated attacker (e.g., connect to the digital I/O's driving
the video/audio buffers).

In the model (analogy) I put forward, I wanted to draw attention to
the act that this was intended solely to "act as an efficient, LONG
wire" -- "piercing the insulation" to tap the signals was a real
possibility.

(Besides, that wouldn't be in the *spirit* of an open source project!)

[Don Y]

Hi Andrew,

[could you please take the time to elide portions of messages
that aren't pertinent to your replies? Thanks!]

On 1/13/2012 8:16 AM, Andrew Swallow wrote:
> On 13/01/2012 05:28, Don Y wrote:
>>>> Every "communication pair" -- i.e., (sender,receiver) -- that
>>>> is active (or POTENTIALLY active) would need such a counter
>>>> in each receiver (I think you can lump all of the "receivers"
>>>> for a particular sender into a single "sender-side" counter).
>>>
>>> Only if it is a multi-drop (like a radio broadcast) and everybody
>>> listens to everything.
>>
>> The server(s) broadcast source content. Clients pick the packets
>> associated with whichever source "channels" they want (based on what
>> they have previously been *told* to want! -- from control messages)
>> and keep track of what they *need* to satisfy their deadlines.
>> If they think they have missed a packet, they request it (from
>> a peer since requesting from the server would scale poorly). If
>> they think a packet that they need wont arrive in time, they
>> begin planning for its absence (so there are no abrupt
>> discontinuities in "playback")
>
> If you only have one or two broadcasts going on at a time then the
> server and the clients only need to remember a couple of broadcast
> sequence numbers. They only need unicast sequence numbers for the
> clients_and_servers they talk to.

At a minimum, each sender needs a counter. I.e., so that *it*
knows what value to use in the next message it emits.

Any communications that are not visible to all potential
receivers need separate counters if any of those receivers
has to infer information from *missing* sequence numbers
(i.e., did I *miss* something?).

Any counter that a receiver can *afford* to ("optionally")
"miss" is an opportunity for a replay attack -- since the
attacker can cause the receiver to see it at a different
time than it was intended to be seen (if the gap between
*known* seen messages is large enough -- like rotating session
keys, etc.)

My architecture treats each functionality as a potentially
separate "sender" (or set of senders).

E.g., the servers responsible for pumping the "source content"
into the mesh can focus *solely* on that activity: pulling
the material off its storage/source media, transcoding as
necessary, and pushing it out to the "clients" at the proper
time. Of course, there can be many such servers operating
alongside each other.

Deciding which clients will subscribe to which "feeds/channels"
can be handled separately. Likewise for configuration changes
and parameter adjustments ("volume up/down" etc.) This means
the source content server needn't be concerned with interactive
issues. And, there is nothing that forces that functionality
to be concentrated in a single physical device (e.g., you could
have a wall mounted "volume control" that just sends volume up/down
messages to the clients known to be present in a particular *room*;
or, allows a user to decide which source programs those clients
should present, etc.)

Global synchronization can be handled by a separate "clock
server" -- ensuring the source media server(s) and client(s)
remain in lock step.

And, of course, the peers with which a particular client
cooperates represent additional "paths".

> The main source may not know that many of the clients exist. The network
> can be split in areas, each area server being responsible for the
> retransmissions in that area. In a big system there could be several
> layers of servers.

No. The whole point is NOT to need more servers to deal with
more *clients*. E.g., a source content server need only be concered
with the number of different "programs" (blech, hard to come up
with a consistent lexicon) it is capable of pushing out onto the
wire in a given unit of time. The fabric assumes responsibility
for getting the data *to* each POTENTIAL client. A radio station
doesn't add another transmitter just because more people in
a given (COVERED) neighborhood TUNE IN to their broadcast!

Having the source content server handle retransmissions makes
it harder to scale the system: the more clients, the more
retransmission requests are LIKELY to be demanded of that
server. The more processing power and bandwidth that server
must reserve for those eventualities (which may or may not
materialize). Instead, you let the server concentrate on JUST
pushing out "source content".

> Each retransmission server will have to keep copies of the packets it
> retransmits.

There's no value added by a "reransmission server". It exists
solely to over dropped packets. If you have none, it is 100%
waste.

>> Since all of the clients (plus the servers) represent a single
>> cooperating "system", they are constantly talking to each other
>> (exchanging performance statistics, synchronizing clocks,
>> rerequesting dropped/corrupt packets, etc)
>>
>> Having all of this intercommunication be BROADCAST would
>> quickly swamp the network. So exchanges between peers
>> are typically unicast (though some of the discovery
>> protocols use multicast/broadcast)
>>
>> If client 1 and client 2 are to talk to each other, they
>> surely can't use the same "sequence counter" that the
>> server was using to talk to all of them -- since the
>> server could be changing it "as they speak".
>>
>> Likewise, client 2 and client 3 can't use the counter
>> that client 1 and 32 are using.
>
> Your packet headers will have to include a field that says if the packet
> is a broadcast packet or a unicast packet. Then the computer looks at
> the record for that broadcast_ID or client_ID to find the requited
> sequence number. There will also be transmission sequence numbers and
> reception sequence numbers for unicast calls.

Each node (client or server) needs to look at a "communication path
ID" to determine what (local) sequence number applies. I.e., its
like maintaining TCP connections. Cost grows with number of
connections.

>>>> If I have to carry lots of state for each potential connection,
>>>> then I need to develop a protocol whereby each client can
>>>> establish -- and register -- the peer relationships that
>>>> it will track going forward. And, a mechanism for reseeding
>>>> those relationships over time (.e., when clients are powered
>>>> up/down or move to alternate "source subscriptions")
>>>
>>> This depends on the level of reliability your network needs. Does it
>>> matter to your clients that they get an entire song?
>>
>> Does it matter if the people in YOUR part of the building hear
>> the evacuation announcement?
>
> Then the server needs to tell the client that it has finished. Without
> the end_of_message packet the client knows after a timeout that a packet
> has been lost.

*Every* (source media) packet has a deadline -- it's HRT! If
a particular packet isn't present when you need it (which might be
some time *before* you are actually going to "play/display" it),
then it is immaterial whether or not it *ever* arrives; HRT means
its value is 0 at that point/thereafter.

Control packets have different requirements. Some are implicitly
acknowledged. Others can be dropped with little practical
consequences (their absence can be noted -- "Hey, I haven't
received an update from Fred in quite a while..." -- and
worked around).

The whole point is NOT to design a system that *needs* (relies upon)
"expensive" mechanisms when "cheap" ones are just as effective.

> There have been packet switching and Store & Forward systems since the
> Second World War I am surprised that one of these does not fit your
> requirements. Or at least supply a good protocol.

Most of the techniques that I have used are commonplace. Some are
only practical in this scale/domain in recent years. Others have
never been applied in the same conditions (though the science behind
them remains valid at these operating points)

[Andrew Swallow]

Radio stations do not have rebroadcast facilities for lost packets.
By having retransmissions you have designed out that architecture.

> Having the source content server handle retransmissions makes
> it harder to scale the system: the more clients, the more
> retransmission requests are LIKELY to be demanded of that
> server. The more processing power and bandwidth that server
> must reserve for those eventualities (which may or may not
> materialize). Instead, you let the server concentrate on JUST
> pushing out "source content".
>
>> Each retransmission server will have to keep copies of the packets it
>> retransmits.
>
> There's no value added by a "reransmission server". It exists
> solely to over dropped packets. If you have none, it is 100%
> waste.
>

You need to think through that area again.

So your plan is to drop the link/path if a client receives nothing for x
seconds.

> Control packets have different requirements. Some are implicitly
> acknowledged. Others can be dropped with little practical
> consequences (their absence can be noted -- "Hey, I haven't
> received an update from Fred in quite a while..." -- and
> worked around).
>
> The whole point is NOT to design a system that *needs* (relies upon)
> "expensive" mechanisms when "cheap" ones are just as effective.
>

You have not done the mathematical analysis that will show you what is
expensive and what is cheap.

[Don Y]

On 1/15/2012 4:51 PM, Andrew Swallow wrote:

> You have not done the mathematical analysis that will show you what is
> expensive and what is cheap.

Wow, I sure wish *I* was clairvoyant (even if it was only a delusion!)

[Christopher Head]

On Sun, 15 Jan 2012 13:34:58 -0700
Don Y <th...@isnotme.com> wrote:

> > Never use the same key for CBC-MAC authentication and CBC
> > encryption.
>
> Why?

(1) In general, the same key should not be used for two purposes unless
they were designed to work together, because an attacker may be able to
examine the outputs of both processes to find a weakness that does not
exist in either process independently.

(2) In the specific case of CBC-MAC and CBC encryption, this is true to
an extreme extent: as explained better on the Wikipedia article on
CBC-MAC, which shows the math, one can arbitrarily modify all but the
last block of ciphertext in such a situation and the mathematical
relationship between CBC and CBC-MAC will ensure that the final
plaintext block, after decryption, turns into something which, although
basically a random pile of bits, "fixes" the running CBC-MAC to return
a positive verification.

The reason for this is essentially that CBC takes the plaintext to be
secret and the ciphertext to be public, CBC-MAC takes the ciphertext to
be secret except for the last block. When different keys are used, the
ciphertexts have nothing to do with each other, so this doesn't matter;
when the same key is used for both, the ciphertext upon which CBC-MAC
relies is the very ciphertext that CBC reveals.

Chris

[Don Y]

Hi Christopher,

On 1/15/2012 8:09 PM, Christopher Head wrote:
> On Sun, 15 Jan 2012 13:34:58 -0700
> Don Y<th...@isnotme.com> wrote:
>
>>> Never use the same key for CBC-MAC authentication and CBC
>>> encryption.
>>
>> Why?
>
> (1) In general, the same key should not be used for two purposes unless
> they were designed to work together, because an attacker may be able to
> examine the outputs of both processes to find a weakness that does not
> exist in either process independently.

Understood.

> (2) In the specific case of CBC-MAC and CBC encryption, this is true to
> an extreme extent: as explained better on the Wikipedia article on
> CBC-MAC, which shows the math, one can arbitrarily modify all but the
> last block of ciphertext in such a situation and the mathematical
> relationship between CBC and CBC-MAC will ensure that the final
> plaintext block, after decryption, turns into something which, although
> basically a random pile of bits, "fixes" the running CBC-MAC to return
> a positive verification.

<frown> But doesn't this only apply when the same message/message
stream is proessed with each?

E.g., if I encrypt M1 with the key -- and send it to "somebody" -- and
independently use the same key to authenticate some *other* message
to "somebodyelse", does this attack still apply? (even if an attacker
can see both transmisions)

[Christopher Head]

On Mon, 16 Jan 2012 12:57:03 -0700
Don Y <th...@isnotme.com> wrote:

> > (2) In the specific case of CBC-MAC and CBC encryption, this is
> > true to an extreme extent: as explained better on the Wikipedia
> > article on CBC-MAC, which shows the math, one can arbitrarily
> > modify all but the last block of ciphertext in such a situation and
> > the mathematical relationship between CBC and CBC-MAC will ensure
> > that the final plaintext block, after decryption, turns into
> > something which, although basically a random pile of bits, "fixes"
> > the running CBC-MAC to return a positive verification.
>
> <frown> But doesn't this only apply when the same message/message
> stream is proessed with each?
>
> E.g., if I encrypt M1 with the key -- and send it to "somebody" -- and
> independently use the same key to authenticate some *other* message
> to "somebodyelse", does this attack still apply? (even if an attacker
> can see both transmisions)

In this case I suppose the attack doesn't apply, but generally in most
protocols (maybe not yours, but in most) you want to both encrypt and
integrity-protect all messages. I'd avoid it anyway, just in case; if
you must live with just one key being preinstalled on each device (not
a problem for you anyway, I think), I'd use it as a master key and apply
a diversifier (I think that's the right word) to get an encryption
subkey and a MAC subkey (e.g., for some hash function H, K_enc = H(1 ||
K_master) and K_mac = H(2 || K_master)).

Chris

[Don Y]

Hi Christopher,

>>> (2) In the specific case of CBC-MAC and CBC encryption, this is
>>> true to an extreme extent: as explained better on the Wikipedia
>>> article on CBC-MAC, which shows the math, one can arbitrarily
>>> modify all but the last block of ciphertext in such a situation and
>>> the mathematical relationship between CBC and CBC-MAC will ensure
>>> that the final plaintext block, after decryption, turns into
>>> something which, although basically a random pile of bits, "fixes"
>>> the running CBC-MAC to return a positive verification.
>>
>> <frown> But doesn't this only apply when the same message/message
>> stream is proessed with each?
>>
>> E.g., if I encrypt M1 with the key -- and send it to "somebody" -- and
>> independently use the same key to authenticate some *other* message
>> to "somebodyelse", does this attack still apply? (even if an attacker
>> can see both transmisions)
>
> In this case I suppose the attack doesn't apply, but generally in most
> protocols (maybe not yours, but in most) you want to both encrypt and
> integrity-protect all messages.

Yes. In my case, I don't worry about protecting "content". (This,
technically, exposes some vulnerabilities but I have covered them
elsewhere in the implementation.)

> I'd avoid it anyway, just in case; if
> you must live with just one key being preinstalled on each device (not
> a problem for you anyway, I think), I'd use it as a master key and apply
> a diversifier (I think that's the right word) to get an encryption
> subkey and a MAC subkey (e.g., for some hash function H, K_enc = H(1 ||
> K_master) and K_mac = H(2 || K_master)).

I was originally thinking along those lines for a key exchange
protocol. But, I think I've discovered a way to implement that
mechanism independently for (reasonably) "low cost".

Thanks! I think I now have everything I need to weave more than
enough security into the protocol (without increasing cost, etc.).

--don

[Ben Livengood]

On Jan 26, 3:02 pm, Don Y <t...@isnotme.com> wrote:
>>> E.g., if I encrypt M1 with the key -- and send it to "somebody" -- and
>>> independently use the same key to authenticate some *other* message
>>> to "somebodyelse", does this attack still apply? (even if an attacker
>>> can see both transmisions)
>
>> In this case I suppose the attack doesn't apply, but generally in most
>> protocols (maybe not yours, but in most) you want to both encrypt and
>> integrity-protect all messages.
>
>Yes. In my case, I don't worry about protecting "content". (This,
> technically, exposes some vulnerabilities but I have covered them
> elsewhere in the implementation.)

What if the attacker happens to be one of the somebody's or
somebody else's you are sending encrypted messages to?
Is there any restriction on which devices can be recipients
of the stream from a given source device and therefore have
access to the secret key used for authentication?

From one of your earlier posts:
> I can embed secrets in the devices on each end of the
> process. Though the design of those devices itself
> is entirely open (the resulting devices will be released
> as open source hardware/software so *anyone* could
> design something to coexist -- peacefully or otherwise - on
> the same wire.

I'm kind of late to this discussion but after reading over the
thread it looks like you want to prevent attackers
from forging the data stream from a source to its recipients.
All that an attacker needs to know in order to forge the stream
is the secret key used for authenticating the stream. When using
an HMAC or any other symmetric cryptographic primitive any of
the recipients who can verify the stream can also forge it.
Maybe I'm missing something, but to me it seems like you would
need to use a public key algorithm for signing the stream so
that each source can keep its signing key secret. This doesn't
mean you have to sign each packet; a HMAC hash chain could
be formed over a sequence of packets and signed at regular
intervals appropriate to the hardware requirements.

Additionally, if you want to be able to securely update devices
you will either need a database of every device's unique secret
key that no attacker could obtain (except for his or her own
device) or else sign your firmware updates with your private
key and make your public key trusted by all the devices. To
do otherwise is presenting a ready-made botnet to the first
attacker to find the secret key used to remotely update the
firmware on all the devices.

Ben

[Don Y]

Hi Ben,

On 2/7/2012 4:19 PM, Ben Livengood wrote:
> On Jan 26, 3:02 pm, Don Y<t...@isnotme.com> wrote:
>>>> E.g., if I encrypt M1 with the key -- and send it to "somebody" -- and
>>>> independently use the same key to authenticate some *other* message
>>>> to "somebodyelse", does this attack still apply? (even if an attacker
>>>> can see both transmisions)
>>
>>> In this case I suppose the attack doesn't apply, but generally in most
>>> protocols (maybe not yours, but in most) you want to both encrypt and
>>> integrity-protect all messages.
>>
>>Yes. In my case, I don't worry about protecting "content". (This,
>> technically, exposes some vulnerabilities but I have covered them
>> elsewhere in the implementation.)
>
> What if the attacker happens to be one of the somebody's or
> somebody else's you are sending encrypted messages to?

If the attacker is one of the intended recipients, the system
has already been compromised. I.e., that device could start
playing Myron Floren music. Or displaying videos of carnal
relations between dogs and cats. Or, "whatever".

> Is there any restriction on which devices can be recipients
> of the stream from a given source device and therefore have
> access to the secret key used for authentication?

How do you propose that restriction? Filtering MAC addresses
(which could be spoofed)? The stream is available to anyone who
connects to the network.

The *secret(s)*, however, are only distributed to clients
intended to receive them!

> From one of your earlier posts:
>> I can embed secrets in the devices on each end of the
>> process. Though the design of those devices itself
>> is entirely open (the resulting devices will be released
>> as open source hardware/software so *anyone* could
>> design something to coexist -- peacefully or otherwise - on
>> the same wire.
>
> I'm kind of late to this discussion but after reading over the
> thread it looks like you want to prevent attackers
> from forging the data stream from a source to its recipients.

The protocol just acts as a virtual wire. Aside from DoS
attacks (which would have to be protected in the switch),
I don't want an attacker to be able to alter the content
or presentation of the material distributed over that
virtual wire.

E.g., I don't want to hear Myron Floren when I expect to
be listening to The Doors (*ever*, for that matter! :> ).
I don't want to rattle the windows when listening to Bach. I
don't want to see "Max Headroom" style stutter effects when
watching _Buckaroo Banzai_. Etc.

> All that an attacker needs to know in order to forge the stream
> is the secret key used for authenticating the stream. When using

Yes. And all you need to steal my car is my car keys! :>

> an HMAC or any other symmetric cryptographic primitive any of
> the recipients who can verify the stream can also forge it.

Correct.

> Maybe I'm missing something, but to me it seems like you would
> need to use a public key algorithm for signing the stream so
> that each source can keep its signing key secret. This doesn't

Why? Who is going to disclose the key to an "unwanted client"?

[Don't think in terms of distributing content to PC's -- who
could misuse and redistribute the information you've given them.
Instead, think more along the lines of your TV "leaking" that
information to your *toaster*! :-/ ]

> mean you have to sign each packet; a HMAC hash chain could
> be formed over a sequence of packets and signed at regular
> intervals appropriate to the hardware requirements.

The problem there is that the yet-to-be-verified sequence of
packets has a short length (in terms of bytes *and* time).
You're not pushing megabytes of data to a client that it can
verify and reproduce at its leisure.

Instead, you are pushing short packets to a client with severely
limited (and FIXED!) resources and expecting that content to be
reproduced "real soon, now" (there are hard deadlines involved).

Phone rings. Music is attenuated as you answer the incoming call.
Caller's voice is routed through audio distribution system. How
much latency do you add to the "sequence of packets" to be signed
before you allow the client to reproduce the caller's voice?

> Additionally, if you want to be able to securely update devices
> you will either need a database of every device's unique secret
> key that no attacker could obtain (except for his or her own

The server already knows all of this. Remember, this isn't
an "open" system that anyone can "subscribe to" (see the
original boombox analogy). Bring one of these devices over
from *your* house and connect it to the network. And it will
just "get warm" (i.e., dissipate power) -- since it doesn't
"belong" here.

OTOH, *gift* that device to me and I will *make* it "belong"!

You can freely design a device that will *play* the content
that it "snoops" off the network -- since the content isn't
encrypted and the design is fully disclosed. (though *you*
are not afforded the protection from interference that the
legitimate clients have)

[I.e., take the code and port it to a laptop. Plug the
laptop into the network and pull the plaintext content
onto a disk drive. Port the decoder to that same laptop
and you can reproduce the content at will!]

[Don Y]

Hi Christopher,

[revisiting this post]

On 1/15/2012 8:09 PM, Christopher Head wrote:

So, implementing a key exchange protocol (in addition to the
previous issues) with just the one secret is a recipe for disaster!
(right?)

[Christopher Head]

If you're using the keys for CBC and CBC-MAC, then yes, that would be
a big problem. You can always use a key exchange protocol like
Diffie-Hellman to make more than one key, though (you can either make a
really big key and break it in half or you can make a big "premaster"
key and then take K1 = H(1 || PMK), K2 = H(2 || PMK), etc.; note that
the output of raw Diffie-Hellman isn't suitable for use as a
symmetric key directly because it represents an integer and not a
collection of random bits, so even if you use the first method you want
to hash the output and the slice up the hash). Way beyond what you
need, though; just preinstall both keys all your boxes and you're set!

Chris

[Don Y]

Hi Christopher,

Yes, exactly. I was just amused as I *started* down the road using
the single key and heard the words of your previous warning echoing
through my mind: "*Ah*, so *that's* what he meant!" :>

Thanks!
--don