Tiny block ciphers for embedded systems

Thanks for that. Humm... I wonder what those marking patterns are actually used for... Well, I guess if law-enforcement stumbles across a image of something disgusting, they can potentially track the unique-id of the printer that actually rendered it, and then try and track down the low-life that owns it. That's would be fine by me.

You have a large legacy database, stored on an embedded system that uses a wimpy underpowered microprocessor? Wow. I've never heard of a combination like that. Is this for real? Did I misunderstand?

Your best bet is probably to choose a tweakable block cipher with the appropriate block size, and throw as much information as possible into the tweak. (e.g., you might include things like the RowID and ColumnID in the tweak) This will mitigate the inherent weaknesses of using ECB mode to encrypt the data in each field.

If you have an ordinary desktop CPU it's not too hard to construct a high-security tweakable block ciphers of any desired block size.

One other option is to add a layer of indirection. Suppose the database has a 30-bit field and currently stores, say, a SSN in that field. You might instead generate a unique 30-bit ID (it could be generated from a counter), store the 30-bit ID in that field, and then have a separate table that maps the 30-bit ID to the encryption of the SSN. This will eliminate the length constraints because the separate table can hold arbitrary-length ciphertexts. That would eliminate the really hard constraints and make it easier to use standard, highly secure encryption algorithms. Have you considered that kind of approach?

I agree that stream ciphers are not suitable: reusing the stream cipher keystream to encrypt multiple values in the database will be a giant security hole.

I absolutely disagree: I think this is not a good usage of ciphers with a tiny block size. I think this is not a good examlpe.

Do you have a real application or is the question you are asking more academic and anticipatory? Either way is fine, but it leads to a different set of answers. If you have a real application, then we don't get to question your constraints and requirements. But if you are talking about an anticipatory scenario then we certainly do. I get the impression you are talking about this in an academic, anticipatory sense. In that case I'm going to question some of the requirements/constraints that you are trying to impose.

Legacy database do exist, it belongs to a customer of the company where I worked previously, and it runs on quite powerful servers (a cluster of 4-processor boxes). When I was doing a different contract for that company, we had discussion about what would it take to add privacy protection to their system... but that privacy protection work was never done. After this discussion I got an idea and developed the cipher during 2 weeks of my summer wacation in 2006 simultaneusly writting an article which I sent to Indocrypt... which got accepted. The cipher was never used in real application and probably will never be. I still believe that the cipher is quite interesting tool, but frankly

- I don't care. I sure made me sound ridicilous in some parts of the thread, so I should probably stop here.

-Valery

On Nov 16, 6:55 am, snipped-for-privacy@taverner.cs.berkeley.edu (David Wagner) wrote:

Just wanted to add one last remark on TinyPRP. The article describing cipher design was reviewed by good/known cryptographers, and they all said that cipher desing is solid. I also did security analysis of the cipher mostly by following secuity analysis of Rijndael (wich was posible because design of TinyPRP is based on design of AES with some adjustment for the small block size). The analyse didn't get into the article due to size limit. According to my analysis and my tests, TinyPRP should be immune to linear and differential analysis, as well as it should be protected from related keys and slide attack. Some other attacks was also considered in cipher design. During Indocrypt I have also discussed it with some good cryptographers, and they told that cipher does look solid... I'm not a professional cryptographer and I'n not working with cryptography directly. Cryptography is just my hobby and I know it very well for amateur. It could be that I did mistake in my analyse, but as i already wrote - read the article, it has very good description of cipher. I'll send cipher implementation to anyone interested and when it concerns cryptoanalysis - you can even enumerate and try every possible trail with this cipher, which is impossible with ciphers like AES. Since TinyPRP reuses many elements and concepts from Rijndael(AES), this analysis may also confirm strength of AES or reveal some of its weaknesses (if any).

Don't bash the cipher because of the author.

-Valery.

But how is it going to permute points of the curve in a way that the ciphertexts will also land at the same curve? Isn't the range of such cipher will be an interval?

Sergei

By using cycle-walking mode of operations. See Black, J., Rogaway, P.:, Ciphers with Arbitrary Finite Domains, In Proceedings of the Cryptographer's Track at the RSA Conference 2002.

Note: cycle-walking is only working for block ciphers.

There is also a theorem that proves that if random permutation is used with cycle walking, then resulting permutation will also be random.

-Valery

Valery, you're now in danger of being placed in the category of people who opens their mouth and makes it obvious that they are stupid, or at least stupidly persistent. :-(

There is nothing magic about binary numbers and encryption, you've had a perfectly good suggestion when you asked about encrypting numbers in the range 0-10k.

Modulo addition does indeed work, please try it and then come back and apologize.

Terje

--
- 
"almost all programming can be viewed as an exercise in caching"

If the input range is [0..10000], inclusive of the end points, then you obviously need to add modulo 10001, otherwise it wouldn't be reversible.

Terje

--
- 
"almost all programming can be viewed as an exercise in caching"

Modulo addition when numbers are from the same set does indeed work. I admitted it yesterday when i wrote that *"i was blind and dumb"*. My appologies (this is something i didn't do yesterday). My mistake was mixing it with modulo operation for making RGN out of random bit generator, where it does create bias.

Whould stream cipher with the stream of numbers in range and modulo addition could be considered as standard stream cipher is another question (because starting suggestion was to stick to standard stream ciphers). And use of stream cipher for encryption in arbitrary domain (like point on curve to another point on curve, or from one valid date to another valid date) is another open question. And I don't think that using Feistel for creating block cipher out of stream cipher will be the answer here.

Thanks for friendly advise, Terje! I appreciate it.

-Valery.

it was another extreamely stupid thing that i wrote yesterday, which i realised a few seconds after i posted. But when send button is pressed, there is no way to remove it. See my answer to myself from yesterday:

"Ok, nevermind - i was blind and dumb."

-Valery

to

between

Thanx, got it! But I'm still wondering, if you want to do it on a curve, even with a cipher that has a small block size, is it practical at all? If the cipher is PRF, aren't chances to hit the same curve too small for any practical use?

Sergei

need to

between

Only PRP works with cycle walking. As for chance to be big enough, the cipher's block size should be bigger, but close enough to the log(amount of points on curve). This is actually the main problem of using standard block ciphers with

64 bits and bigger block size for encrypting a valid date to another valid date in range from 20 to 60 years old - the chance to meet valid date is too low and it may be unfeasible if block size is bigger than 80 bits. However, with appropriate block size it may require just a few iterations. And result is non-expanding typeaware encryption that has the same security level as block cipher that was used with cycle- walking (according to cycle-walking theorem)

-Valery.

Your worried about "10000" because it is a 16 bit example and 16 bits could mean up to 65k binary numbers - the last "5k" meaning that "mod"

10000 will lead to a bias because of more additives below 5k. Yes?

Just keep track of the stream being generated and if it is over 60000 (or 10000) discard it., This is reversible when decrypting because the key stream is generated separately to the data

You were given an answer yesterday that works for this situation too. Given a block cipher that produces numbers about the size of P (the modulus of the underlying EC field), just keep transforming the x coordinate until you get one that is within range and on the curve. This will terminate after an average of around 2-3 encryptions, and is uniquely reversible.

Greg.

--
Greg Rose
232B EC8F 44C6 C853 D68F  E107 E6BF CD2F 1081 A37C
Qualcomm Australia: http://www.qualcomm.com.au

This process is similar to arithmetic compression, in that you can use a stream of random binary bits to generate unbiased numbers in any non-power-of-two range you would like.

The easiest in the current situation is to look for a multiple of the desired range which is close to but not greater than a given power of two, then pick that amount of random bits, check that you're within the desired range, and discard/retry otherwise.

I.e. we want random numbers in the 0-10000 range:

10001^3 = 1 000 300 030 001 ~= 1.0e12 2^40 ~= 1.1e12

So the procedure is to grab 40 bits from the random stream, then check if the resulting number is >= 10001^3: If it is, discard and retry.

When we get a valid sample (which happens more than 90% of the time), we split it apart into 4 individual numbers, all in the 0-10000 range, using div/mod operations.

So what about the 8+% of lost samples?

Each time we get a sample that should be discarded, we can subtract the maximum initial range, and consider the remainder as a random number in a smaller (overflow) range. These overflow values can also be multiplied together and the multiples treated the same way as the original 40-bit samples.

Doing this for multiple levels is where it starts looking like AC to me.

Terje

--
- 
"almost all programming can be viewed as an exercise in caching"

Humm... Well, IMVHO, that seems to be a bit paranoid?

Crypto people don't "hate" stego. They're complementary tools: cryptography attempts to hide the _content_ of a message, while steganography attempts to hide the _existence_ of a message.

Of course, because the biggest concern among spies is not the _content_ of their messages being discovered, but the rather the very _existence_ of the messages. A spy becomes useless (and likely dead) as soon as the enemy knows he's a spy, regardless of whether the enemy can read what he's saying. However, most of us have no need to hide the existence of our messages, just the contents. Aside from terrorists, spies, and cheating spouses, few people care if you know they're talking to someone; they just don't want you listening in on the conversation.

S

--
Stephen Sprunk         "God does not play dice."  --Albert Einstein
CCIE #3723         "God is an inveterate gambler, and He throws the
K5SSS        dice at every possible opportunity." --Stephen Hawking

Whose law enforcement? Korean (N or S) Chinese, US, Russian, Iranian, Iraqi, Libyan Spanish .......

What an LEA (or more probably some one's government) considers "discussing" may vary....

Pro democracy groups in some countries would not be able to print anything for fear of being traced.

It would not be too long before various groups would be abler to forge anyone's printer ID

--
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
\/\/\/\/\ Chris Hills  Staffs  England     /\/\/\/\/
/\/\/ chris@phaedsys.org      www.phaedsys.org \/\/\
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/

Unfortunately history has proven that abuse within a system is far to easy. Take the abuse that happened during the 50s and 60s by the CIA. AFAIU the CIA is supposed to handle "foreign" enemies. Where people's personal rights were trampled. If some bureaucrat decided that YOU were undesirable, then you basically had no recourse. You probably will not even know you have been targeted. The fundumental problem of who will gaurd the gaurds always applies with these sort of things.

Regards Anton Erasmus