Avoiding all zeroes entering a random sequence without any conditional testing

Embedded Security
1

I don’t know if this is the right place to ask such a question. In case not, where?

I have an algorithm that fails on a parameter with all bits being zero. I would like not to test for a zero, to avoid having to set it to some other value “by hand”. I have found no way to do this.

I have tested xor’ing the param with some mask like 0x81 (assuming a byte [0-0xff]). Of course, when I hit the value 0x81 then xor’ing with it yields 0.

If I rotate the mask for every value (example: ROL(0x81,1) = 0x03) then the value 0 will not appear in the data set. But I lose so many of the others. Like for the first 18: 1, 2, 4 (instead of 3), 4, 5, 6, 7, 7 (instead of 8), 9, 10, 12 (instead of 11), 12, 13, 14, 15, 15 (instead of 16), 17, 18…

My question is whether there is any algorithm that will have me lose as few values from the set as possible, ie. minimising the number of duplicates?

Hopefully without any conditional if/then/else? (Or will there be a better conditional test algorithm?)

Maybe it’s not possible to find such an algorithm? NP-complete?

2

I have written some code that loops around and tests all values. I have only worked with a byte value, and ranges [0…255].

I find that there is some kind of pattern with the mask I xor the bit_pattern with. Depending on it there will appear 0-values that I do not want as a result some times, since the initial pattern I xor with must survive “sliding doors” with the bit_pattern. Here is the set I have to chose from:

128 values ok, 64 missed and then 64 counted two times
28 times with no bit_pattern xor mask value becoming zero, starting with these masks:
0x01, 0x04, 0x06, 0x011, 0x014, 0x016, 0x024, 0x025, 0x026, 0x034…

Simply using 0x01 as the mask I xor with, and then rotate to the left (ROL) for each appearing bit_pattern should then probably work for a 32-bit value as well. I just assume it would slide as nicely up to 32 bits as it did for 8 bits.

But the price for not doing a conditional test is high! I loose 1/4 of the range! Or, 1/4 of the values would be mapped over another 1/4, which certainly may be quite confusing if there were some unit listening for what I did(?)

But still, there must be something smarter out there!?

3

Hi Øyvind,

It’s hard to give advice without understanding more about the problem and the context.
Basically you need to map [0,255] to [1,255]? What are the other constraints? How do side-channel attacks come into the picture?
Without knowing more I could suggest you simply set one of the bits of your incoming parameter.

Jean-Pierre

1 Like
4

Thanks, @jpthibault,

Basically you need to map [0,255] to [1,255]? What are the other constraints?

Yes, and …I can’t think of any other constraint.

I am just playing around, really. I am trying to make some side-channel “hiding” for the xCORE (by XMOS) architecture, by letting the other 7 cores work or don’t work at the same time as some encrypting algorithm is running on one core. They would interchange on a cycle basis.

I’ll publish the code when/if I think it worth discussing. (This would be at Task/processes to insert random noise).

I ran into a problem that I think is a problem with the XMOS compiler. I have filed this to XMOS. But I thought it rather interesting, because then I was forced not to “hide” anything with all 32 bits being zero. That sound like a bad “fence” to me. Just one bit as “pole” would be better I thought. Kind of like a noise sender being switched off, even if zero is just as good a random number as any other.

And when I had a rather good random value (32 bits timer in ten nanoseconds resolution) snap-shot from a button I pressed it, I hoped to be able to not remove any of that nice randomness by setting a bit. (I guess this is a premise: that setting a bit destroys more than inverting a bit. XOR in theory does not lose any energy, and it’s therefore also a cipher. Anybody wanting to get these matters straight to me are welcome!) (Another premise I guess is that I did not think having any conditional test on the input set was a good idea. Also, is this a good premise…?) So I was trying with an xor, which would or would not invert bits. Then I in addition have shifted or not shifted the mask I am xor’ing with.

Still your idea triggered something One bit? When I made the xor-mask be only a single bit, bit number taken from the least significant 5 bits of the incoming random 32 bits bit_pattern, I then would invert bit number [0…31]. (For my case I needed to use only 8 bits, to always have a bit to invert.) And the mask would not be rotated for every of the 256 values I tested as the incoming data set. But I got the same result as xor’ing with anything else, any number of bits. Of 256 input values [0…255]:

128 values ok, 64 missed and then 64 counted two times. No zeroes.

There probably is something inherent in this algorithm that would map 1/4 of the data space over the other. So I get 50% unique numbers (call them “middle”) and 50% where I cannot tell if the mapped result orignally belonged to “left” or “right” data set. I can live with it. Maybe it’s even rather good.

I will not mark this thread as solve since I may come back with more here in due time. Or wait for some better idea!

5

Oooh, now you’re deep in the rabbit hole. Generating random numbers is not as easy as it appears to be, and countless systems have been broken as a result of bad random numbers.

I can’t recommend this book enough for learning about the basic dos and don’ts of applied cryptography

No affiliation, it’s just a great book. It’s very approachable to non-experts in the field. It has a chapter on randomness, including a section on “how things can go wrong” :wink:

Jean-Pierre

1 Like
6

Yes, I’m sure I could need that book. Do you know if the rather long errata list (called “Updates”) have been fixed in the eBook version? It’s good with a public errata, but it was rather loong…

(That being said, the random number is not the problem here. I am just using the superfast system clock timer to get something that’s not coming from the random library, even if there should be some kind of HW seed on the xCORE-200. I have a feeling that they have made an even better random generator on the upcoming xcore.ai. (So that the seed also is 100% random, I believe only then is a pseudo-random sequence really useful). I have also been rather interested in nondeterminstic choice in select/case etc. It’s close to the theory of randomness. A blog note here)