Security of HKDF when part of output is exposed

Question

There is a system in which Alice and Bob need to establish a secure communication channel. Their conversation happens via a "public" server whose only purpose is to rely messages between users. This server must never be able to decrypt communications.

With the protocol that Alice and Boo will use, the first time they want to talk, Alice generates a 128-bit key that is able to exchange with Bob in person.

This is the only communication that Alice and Bob can have in a trusted manner (in person) before begin communicating through the server above mentioned. As stated, this communication is one-way (Alice-to-Bob) and Alice is only able to give bob at most 128 bits of data.

Now, Alice and Bob connect to that server and need to find each other by going in the same "stanza". Since the only knowledge that Alice and Bob have of each other to meet is that 128-bit key, they expand this key (using HKDF) to create:

1. A 256-bit AES key for encryption.
2. A 256-bit HMAC-SHA256 key for authentication.
3. A 128-bit "stanza-id" that will be advertised publicly.

Since the server allows any client to choose any arbitrary stanza-id on where to sit and wait for messages, Alice and Bob are able to meet each other in the same stanza, and even if someone is able to listen to them, their communication is secure since it is encrypted and authenticated.

My questions are:

1. Does exposing part of the HKDF output publicly weak the other "private" parts or leak any other information?

2. Does it make sense to use AES-256 when the key originates from only 128-bits of entropy?

3. Does allowing any client to chose any arbitrary stanza-id put the server in danger in any way?

Answer 1

In a secure KDF, the output is indistinguishable from random. In particular, all the output bits are independent, so revealing some of the output doesn't give any indication about the other bits.

Hugo Krawczyk's HKDF definition paper proves that HKDF is a secure KDF under some reasonable assumptions on the underlying hash function which SHA-2 is believed to meet (theorem 4).

With a 128-bit root secret, you only get at most 128-bit protection for anything based on derived material, even if you use a stronger algorithm. That's ok: 128-bit is generally considered unbreakable until at least 2030, and it doesn't get any better than unbreakable.

Allowing clients to pick arbitrary stanza-ids doesn't harm the server directly. It's just passing data through. It means that the server won't be able to use stanza-ids to meter communication, so you'll have to rely on some other means to avoid denial of service attacks (if anybody can submit data to your server, someone can upload terabytes that they won't be using, and you have no way to detect that).

Note that even if the server is unable to make a link between Alice and Bob through pure cryptography, it can make informed guesses by observing who uploads and downloads what data when. It'll take more than this part of the protocol to achieve some measure of anonymity.

I recommend using a proper authenticated encryption mode such as GCM, rather than building your own with AES and HMAC. You have less risk of an implementation mistake that way.