Encrypting using multiple keys in parallel

[mkaluza]

Hi @glenvt18
Since you probably know this library very well, I hope my question won't be a problem for you.
I know that presently bitslice algorithm can process many packets at once, but only one key. Is that a feature of this method or just nobody ever needed to use many keys, so it's not implemented (although it could be).

Our usecase is that we'll be scrambling an MPTS in real time and each service has different keys. Also our batch is small (entire mux output buffer is only 128pkts), so right now much of the processing power would go to waste, because we'd never have 128pkts from one service at a time.

So my question is: Is it possible for the algorithm to encrypt i.e. 2x64 or 4x32 (in sse mode) with two/four different keys at once?

[mkaluza]

And thank you for your work - that kind of speedup is awesome ;) We have Pentium G4560 as a test machine and it achieves 1377mbps in bitslice bench using ssse3 :)

It's a pity your patches weren't merged into the original lib...

have you ever thought about AVX? :) Not that it isn't fast enugh - just for the sake of doing it :)

[glenvt18]

HI @mkaluza
At first glance, multi-keying should work. It will require setting individual bytes in the expanded key's bs_word using masks. It is possible to have up to BS_BATCH_BYTES keys and as low as 8 packets per batch. With the current implementation, packets should be interleaved. For example, 4x32 batch:

s0[0] s1[0] s2[0] s3[0]    s0[1] s1[1] s2[1] s3[1]    ...   s0[31] s1[31] s2[31] s3[31]

where sN[i] means i-th packet of the N-th stream.

Keys can be set up using subsequent calls of something like

void dvbcsa_bs_key_set_mx(const dvbcsa_cw_t cw, struct dvbcsa_bs_key_s *key,
                          int start, int len)

where start and len define the mask. For 4x32 (start, len) can be

start=0, len=4 
start=4, len=4 
start=8, len=4 
start=12, len=4

And you'll have to keep the length of the pcks[] array equal to the batch size (128 for sse). In other words, pcks[i].data shouldn't be NULL for any 0 <= i < 128. It won't hit performance much.
Any suggestions?

AVX (256, 512) should work out-of-the-box after adding AVX intrinsics. If you can test it, I'll add them (or you can submit a PR). I just don't have HW to test.

[nto]

If someone comes up with AVX patches (both AVX2 and 512), I can test them.

[mkaluza]

@glenvt18 Thanks for the reply :) I'll look into it.

As for AVX - I looked at the header files and it doesn't seem complicated, although right now I know nothing about SIMD programming yet, but maybe it's a good time to learn something new. I have i5-6400 and E3-2603 available for testing and benchmarks and they both support AVX2, so I have something to work with. No AVX512 though :(

It seems that for some SSE instructions AVX just made them wider, so maybe it won't be difficult. I'll get back when I have something :)

Thanks for you help

[mkaluza]

@glenvt18 I tried understanding what dvbcsa_bs_key_set does and creating dvbcsa_bs_key_set_mx based on that, but I failed... Could you help me with that if it's not too much trouble? I created a test case for it (I hope I got that packet interleave right) and a stub, but I haven't got any idea about the function :/

https://github.com/mkaluza/libdvbcsa/tree/multikey

[glenvt18]

@mkaluza Sure, I'll do all this work myself. You'll only have to run tests. Is the suggested API OK with you? I really don't want to bloat BS key buffer. I want to keep working buffers as small as possible to minimize cache misses. I think it's better to extend existing test framework (testbitslice).

[mkaluza]

I agree that memory structures should remain as optimal as possible.

But first I'd like to ask about key setting to understand what is possible and what is not, so that I can figure out how to use it and what to avoid. For this example let's assume we have 64bit word width, which means at most 8 keys and each batch 8 pkts wide then.

From most important to least important:

1. Are there any key patterns I can or cannot set? Lets say I have 4 streams (4 keys), with significantly varied bandwidth and I want to allocate batches proportionally to that like so: AAAA BB C D
   Is it possible? Are all widths allowed, or i.e. only power of two? Could I set AAA BB CC D?

2. How intensive computationally is key setting (just roughly - much or little)? Because if it's not, 3) and 3a) don't matter - we can simply always do everything.

3. Can I modify the key? let's say I have AAAA BB C D and I want to have AAA BBB C D - will it be enough to change key[3] or do we have to recalculate everything always?
   3a) if key can be modified, can it be moved? If I have AAAA BB C D and want to have AAA BB CC D, could this be done with key[3:4] = key[4:5]; key[5] = C; or does it have to be key[3] = B; key[5] = C? In this example it makes little difference , but there easily could be a pathological case with 32 (or 64 with AVX512) keys where you'd like to expand the last one at the expense of the first one, which would result in 30 vs 1 calculation.

points 3) and 3a) are absolutly optional - I just want to know what is possble and what is not.

The way I would like to use it on high level is like that (or something like that):

struct cw_list {
  uint8_t cw[8];
  uint8_t len;      //number of bytes, not bits, sums to less than BS_BATCH_BYTES
}
dvbcsa_bs_key_set_multi(struct cw_list cw_list[], struct dvbcsa_bs_key_s *key);

where cw_list array is up to BS_BATCH_BYTES long and is either null terminated or lenth parameter is required - makes no differnce.

I would extend struct dvbcsa_bs_key_s with uint8_t len[BS_BATCH_BYTES]; uint8_t cw_count; to store batch sizes passed to dvbcsa_bs_key_set_multi function. I don't think this addition will impact cache performance as it would be at the and of the (relatively large) structure and not touched during normal operation, but correct me if I'm wrong.

If key modification would be possible, I'd also add uint8_t cw[BS_BATCH_BYTES][8] to struct dvbcsa_bs_key_s and a function to update the keys (can't imagine the syntax right now, besides it's completely optional right now).

That high level function would call the function you write in any way you see fit.

As for de/encryption, I'd like to encapsulate packet interleave inside the API, i.e I'd like to pass an array where each batch of packets is continous, and I'd like the API (multikey versions of dvbcsa_pkt_buf_load and dvbcsa_pkt_buf_store) to handle storing them in the buffer and extracting in the right order (packet interleave is an implementation detail - user should not need to know about it especially if packets are copied anyway).

I'd like the API to accept NULLs as end of batch - the same way it now does with entire list. This way the method signature could stay the same (no need to pass packet counts per batch and no need to set fake pointers and copy garbage data back and forth). And also the behaviour for old single key encryption wouldn't change as well - it would just be a single null terminated batch of BS_BATCH_BYTES width.

And everything below that (dvbcsa_bs_stream_cipher_batch, dvbcsa_bs_block_decrypt_batch, dvbcsa_bs_block_encrypt_batch) is up to you.

There... It's the idea, I'm open to discussion :) If you're fine with it, I'll start implementing that.

[glenvt18]

@mkaluza I've just wanted to ask you about the bandwidth allocation but you asked first:)

Are there any key patterns I can or cannot set? Lets say I have 4 streams (4 keys), with significantly varied bandwidth and I want to allocate batches proportionally to that like so: AAAA BB C D
Is it possible? Are all widths allowed, or i.e. only power of two? Could I set AAA BB CC D?

Yes. You can allocate freely within bs_word. That is, for 64 bit you have 8 slots and can allocate any set within. Constrains: len = [1, 8), start >= 0, start + len < 8. If these are not met I'll call abort(). For example:

AAAAABBC
dvbcsa_bs_key_set_mx(0, 5);
dvbcsa_bs_key_set_mx(5, 2);
dvbcsa_bs_key_set_mx(7, 1);

It's just like setting a bit mast. You can even allocate AAABBBAB.

How intensive computationally is key setting (just roughly - much or little)? Because if it's not, 3) and 3a) don't matter - we can simply always do everything.

Key setup is cheap. You can call it before every encrypt(). This might be helpful when you synchronize key updates: you just have to copy 8 bytes (cw). I've just called it 40 times before every encrypt and didn't notice any change. Run benchbitsliceks to get exact numbers. dvbcsa_bs_key_alloc() might not be that cheap.

Can I modify the key? let's say I have AAAA BB C D and I want to have AAA BBB C D - will it be enough to change key[3] or do we have to recalculate everything always?

Yes: dvbcsa_bs_key_set_mx(2, 1). Think of it like setting a bit mask.

I would extend struct dvbcsa_bs_key_s with uint8_t len[BS_BATCH_BYTES]; uint8_t cw_count; to

dvbcsa_bs_key_s* is an opaque pointer in dvbcsa.h. You don't have access to it's members.

My suggestion:

/* stream */
struct dvbcsa_bs_mx_slots_s {
  int start;
  int len;
  dvbcsa_bs_batch_s *pcks; /* NULL terminated */
};

/* slots are NULL terminated array */
void dvbcsa_bs_key_set_mx(const dvbcsa_cw_t cw, struct dvbcsa_bs_key_s *key,
                                               struct dvbcsa_bs_mx_slots *slots);

void dvbcsa_bs_encrypt_mx(const struct dvbcsa_bs_key_s *key,
                       const struct dvbcsa_bs_mx_slots_s *slots,
                       unsigned int maxlen);

This ensures you use the same slots for key setup and encryption.

EDIT Or even better

/* stream */
struct dvbcsa_bs_mx_stream_s {
    dvbcsa_cw_t cw;  /* key for the stream */
    int start_slot;
    int n_slots;
    dvbcsa_bs_batch_s *pcks; /* data=NULL terminated */
};

/* streams are NULL terminated array */
void dvbcsa_bs_key_set_mx(struct dvbcsa_bs_key_s *key,
                          struct dvbcsa_bs_mx_stream_s *stream);

void dvbcsa_bs_encrypt_mx(const struct dvbcsa_bs_key_s *key,
                          const struct dvbcsa_bs_mx_stream_s *streams,
                          unsigned int maxlen);

EDIT. This is also possible (and looks better):

/* stream */
struct dvbcsa_bs_mx_stream_s {
    dvbcsa_cw_t cw;  /* key for the stream */
    int start_slot;
    int n_slots;
    dvbcsa_bs_batch_s *pcks; /* data=NULL terminated */
};

void dvbcsa_bs_key_set_mx(struct dvbcsa_bs_key_s *key,
                          struct dvbcsa_bs_mx_stream_s *stream);

void dvbcsa_bs_encrypt_mx(const struct dvbcsa_bs_key_s *key,
                          const struct dvbcsa_bs_mx_stream_s *streams,
                          int n_streams,
                          unsigned int maxlen);

You have to keep one dvbcsa_bs_key_s buffer storage per thread. (call dvbcsa_bs_key_alloc once). Take it like a space in the tread stack.

[mkaluza]

Ok, it seems fine with few adjustmens below (move cw into struct slot, removed 's' from the name), . This way it'll be easy for the user as the key and batch description and pointer will be all in one place and will be easy.

Key setting is indeed cheap - my cpu can do 4,2M/s, which gives .25us, when the whole cycle takes around 180us. I don't care about alloc as I assume I have to do it only once.

/* stream */
struct dvbcsa_bs_mx_slot_s {
  int start;
  int len;
  dvbcsa_cw_t cw;
  dvbcsa_bs_batch_s *pcks; /* NULL terminated */
};

/* slots are NULL terminated array */
void dvbcsa_bs_key_set_mx(struct dvbcsa_bs_mx_slot_s *slots,
                          struct dvbcsa_bs_key_s *key);

void dvbcsa_bs_encrypt_mx(const struct dvbcsa_bs_key_s *key,
                          const struct dvbcsa_bs_mx_slot_s *slots,
                          unsigned int maxlen);

I'm only thinking about renaming len to width - it's more width in fact and it would also be less confusing - len might be mistaken as describing the length of pcks . Or size?

[glenvt18]

@mkaluza How about my latest (edited) suggestion with dvbcsa_bs_mx_stream_s, n_slots, n_streams?

[mkaluza]

looks very good :)

I only wonder why dvbcsa_bs_encrypt_mx has n_streams param, while dvbcsa_bs_key_set_mx doesn't? I'd move it to dvbcsa_bs_key_set_mx, which can store it inside struct dvbcsa_bs_key_s - after all it's something that won't change independently of the key, so it can be provided only once and stored there. It's a part of the structure of streams that you define and change only when setting the keys. On the other hand keeping data pointers inside struct dvbcsa_bs_mx_stream_s and accessible to the user, as you suggested, is justified as they can (and will) change, but as long as the structure remains the same, everything is ok.

And struct dvbcsa_bs_key_s would remain an opaque pointer - number of streams would only be passed as a param to dvbcsa_bs_key_set_mx and later retrieved by encrypt/decrypt functions, so it'd be used only internally.

[glenvt18]

@mkaluza

I only wonder why dvbcsa_bs_encrypt_mx has n_streams param, while dvbcsa_bs_key_set_mx doesn't?

dvbcsa_bs_key_set_mx takes a single stream.

I'd move it to dvbcsa_bs_key_set_mx, which can store it inside struct dvbcsa_bs_key_s

dvbcsa_bs_key_s doesn't care of the number of streams. The allocated storage is always the same constant size (~batch size * bs_word size). Its purpose is storing expanded keys in the internal properly aligned buffers.

[mkaluza]

ok, it's clear now :)

There's one more thing. Would it be possible to add bounds checking to mx equivalent of dvbcsa_pkt_buf_load/store?
Here: https://github.com/glenvt18/libdvbcsa/blob/master/src/dvbcsa_bs_algo.c#L48.
So that when it is copying packets, it'll stop when encountering NULL OR when i == stream->n_slots * 8.

Why? Knowing that I can never process more than BS_BATCH_SIZE packets at one time anyway, I can allocate one pcks[BS_BATCH_SIZE] array and only update stream->pcks pointers. But if a stream was completely filled, there would be no space for NULL terminator (it would be a start of another stream).

That way NULL would only be used to signal that there are less packets that can fit the stream, but it would never try to read more (I think that is a good thing in general...)

[glenvt18]

@mkaluza In this case it's easier to add n_pcks to dvbcsa_bs_mx_stream_s. And it is more flexible as well. Do you agree?

[mkaluza]

I thought leaving null termination and adding bounds check would be an extension to the old api to avoid confusion, but I'm not attached to any solution as long as it gets the job done :) n_pcks is more explicit, NULL is more 'the old way', but equivalent - it's your lib, pick the one you like more :)

EDIT: If I were to decide, I'd leave NULL + bounds check