Tiny block ciphers for embedded systems

Add mod 10000 will give bias because values above 10000 will contribute to interval 0...n-10000. Also remember bit flipping. With block cipher you can encrypt value between 0 and 10000 to a value between 0 and 10000 and it will be PRP. With stream cipher you can't do that. Bock cipher allows to encrypt points of quite weird domain to the point of that domain. Ex. you can encrypt point on curve to another point on this curve and it will be PRP. And there is a theorem that proves that if PRP is used with cycle- walking mode of operation, the resulting transformation is also PRP.

-Valery.

Reply to
Valery Pryamikov
Loading thread data ...

Wouldn't it be better to discard any value between 10001 and 16384? modulo addition seems like it would bias the result towards the first 6384 numbers.

--
Guy Macon
Reply to
Guy Macon

No, the stream itself would be of numbers 0-10000. There would be no higher numbers. It would be a number stream, not a bit stream. If you are using terms like PRP and know what they mean, I'm sure you can understand the above concept too.

Reply to
Paul Rubin

Even so the stream consists of numbers between 0 and 10000 we need to add them somehow to the source number and get number in range between

0 and 10000. Bitwise addition doesn't work will generate number above 10000 (ex 9999 XOR 1024 = 10127) and addition mod 10000 give bias (ex 9999+1024 mod 10000). And 0...10000 is the easy domain. Try using stream cipher to create PRP on the points of curve.

-Valery.

Reply to
Valery Pryamikov

Discarding numbers work very well for generation of random number in range. However it doesn't solve problem of encryption of points of the domain (here we need PRP).

-Valery.

Reply to
Valery Pryamikov

Typo correction. I actually mean 9999 XOR 128 (not 1024).

9999 XOR 128 = 10127; and 9999+128 = 10127, means that 9999 + 128 MOD 10000 adds to bias.

-Valery

Reply to
Valery Pryamikov

Should read 128 instead 1024 in prev letter.

9999 XOR 128 = 10127; 9999+128 = 10127 ....

-Valery

Reply to
Valery Pryamikov

Get your story straight, please.

Phil

--
Dear aunt, let's set so double the killer delete select all.
-- Microsoft voice recognition live demonstration
Reply to
Phil Carmody

I thought it was straight... even so it doesn't help when it is quoted out of context ;). "values above 10000" come as answer to suggestion to use stream cipher with some addition operation (the thing that was clipped out) ;) my answer was that adition operations either move resulting value out of domain 0...10000, or introduce bias if used with mod 10000. Of course it is posible to make PRP out of PRF with help of Feistel, but that was not even suggested xD... And my story is that block cipher with small block size could be a very useful tool for some scenarios. Adding Feistel on top of standard stream cipher will slow it down and puts extra demands on embedded hardware. I think that carefully designed block cipher with small block size is better solution for that. And additionally, if we talk about 16 bits block cipher - it could be a very good toy for learning linear and differential cryptoanalysis - you can even enumerate and try every possible trail on such chipher xD.

-Valery.

Reply to
Valery Pryamikov

What bit of Paul's statement wasn't clear?

Phil

--
Dear aunt, let's set so double the killer delete select all.
-- Microsoft voice recognition live demonstration
Reply to
Phil Carmody

Think more.

Phil

--
Dear aunt, let's set so double the killer delete select all.
-- Microsoft voice recognition live demonstration
Reply to
Phil Carmody

Thanks ;) may be you should take on your own advise and think more yourself ;).

-valery

Reply to
Valery Pryamikov

Phil, take on your own advise - it does help to read and think a bit before answering ;)

-Valery

Reply to
Valery Pryamikov

That's hardly an answer. Which bit of adding numbers in [0..10000) to numbers in [0..10000) modulo 10000 are you having difficulty with?

Phil

--
Dear aunt, let's set so double the killer delete select all.
-- Microsoft voice recognition live demonstration
Reply to
Phil Carmody

bias on number 9999. (9999+9999) mod 10000 = 9998

-Valery

Reply to
Valery Pryamikov

Of course, you can eliminate that bias (9999 appearing less ofthen then the rest of numbers) if you will be adding numbers in ( [0...10000) to numbers in [0...10001) ) mod 10000, but that was not suggested, wasn't it?

-Valery

Reply to
Valery Pryamikov

And?

(0 +9998) == 9998 (1 +9997) == 9998 ... (9998+0 ) == 9998 (9999+9999) == 9998

So you see there are precisely 10000 ways of achieving 9998 as a sum.

Which is precisely the same number of ways that there are of achieving any other number as a sum.

So there's no bias.

"it does help to read and think a bit before answering"

One of us knows that. The other is hopefully in the process of learning that.

Phil

--
Dear aunt, let's set so double the killer delete select all.
-- Microsoft voice recognition live demonstration
Reply to
Phil Carmody

Now, all said about bias, (and how to avoid it on this simple domain [0...10000) ), try to use stream cipher to permute points of curve, or to permute birtdays in range 20-60 years old, so that you can reverse this permutation afterward... Saying "use Feistel" would not be an answer, because you create PRP out of PRF and that's different beast than just using standard stream cipher...

-Valery

Reply to
Valery Pryamikov

Was i saying bias on number 9998? lol. I wrote about bias on number

9999 because you get this number less ofthen then any others if you use [0...10000) + [0...10000) mod 10000.

Count it.

-Valery

Reply to
Valery Pryamikov

Ok, nevermind - i was blind and dumb. point about encryption in arbitrary domain with stream cipher still stands.

-Valery

Reply to
Valery Pryamikov

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.