Tiny block ciphers for embedded systems

In 99.9% cases the ciphers are used because of the fascination about the secrecy and the overblown sense of the self importance. Those are the typical attributes of the stupidity and immaturity, that's why there are so many flawed implementations around :-)

Sure. It is good to know the limits of oneself.

Good for you. Why didn't you start then with the "Applied Cryptography" by Schneier?

WTF are you talking about?

XTEA is 64 rounds of Feistel, and this is a problem. Very slow and no prospective to speed up.

Vladimir Vassilevsky DSP and Mixed Signal Consultant

formatting link

Reply to
Vladimir Vassilevsky
Loading thread data ...

Hi, TinyPRP

formatting link
seems to be the cipher that fits to your requirements. The cipher is based on AES and adjusted for small block size (16 and

32 bits). Overall it has the same structure as AES (MixRoundKey-SubBytes- ShiftRows-MixColumns, where the last two was changed to ShiftCells, MixCells due to small block size) and uses same sboxes and polinomials as AES. Major differences is in design of linear mixing transfomration (ShiftCells-MixCells) and keyschedule is different to counter low entropy of round keys. Keyschedule uses the same SubBytes-ShiftCells- MixCells to ensure that every bit of round key r+2 depends on every bit of round key r. According to my analysis of the TinyPRP cipher - it is immune to linear and differential cryptoanalysis and I got quite good feedback on this cipher from several cryptographers at Indocrypt 2006.

Note: I'm not working for Harper Security Consulting anymore and website with the article and source code is down, but I can send you both article and source code (non-optimized) if you are interested.

-Valery

Reply to
Valery Pryamikov

I didn't find interesting at a previous time. Now i'm reading "Handbook of applied cryptography". I will have a look at what you suggested as well.

I mean you want to make money and not share useful information. It is understandable. Lying and/or exaggerating is not.

Of course it is not easy to speedup, due to the dependencies among consecutive rounds. Bitslice ciphers are ideal, but have even more problems with security. AES has good parallelization (i have my own tools to analyze applications for intrinsic parallelism at basic-block level). I think i need a compiler for my processor before targeting it first. The XTEA implementation was 110 assembly instructions for my processor (hand coded).

Nikolaos Kavvadias

Reply to
Uncle Noah

In message , Vladimir Vassilevsky writes

Also a cypher only has to protect the information from the attacks it is likely to have over the time the information is valuable.

Many of the ciphers were developed to fill a need but the ability to defeat them in a required time has over taken them

Play nicely children... :-)

See

formatting link
click the Ciphers button for most of the sources for the book.

--
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
\/\/\/\/\ Chris Hills  Staffs  England     /\/\/\/\/
 Click to see the full signature
Reply to
Chris Hills

Hi Valery

thank you for your post. TinyPRP looks like well within my requirements. I was able to download the paper from my university office (from the proceedings site). I would be interesting in your reference code.

Can you see my e-mail from my information here?

Good! I'll read your work! Of course you can expect reference to your work (in case i use it) in both my Ph.D. thesis (unfortunately only in Greek) and any future works.

Kind regards Nikolaos Kavvadias

Reply to
Uncle Noah

On Nov 13, 3:30 pm, Guy Macon wrote:

There are many things that could be done with block cipher, but that can't be done with stream ciphers. Block ciphers acts as PRP (no collisions between ecrypted blocks), while as stream cipher are PRF (collisions are expected at square root boundary). Bit-flipping affects only flipped bits with stream cipher and it affects entire block with block cihper... Plus more. You can use block ciphers with cycle-walking mode of operation, stream ciphers can't be used with cycle-walking mode of operations at all. For example, block ciphers (in cycle-walking mode) could be used for type-aware non-expanding encryption of fields in database, such as credit cards numbers or birthdays. Block ciphers could be used for generation of non-colliding random numbers (transaction number or credit card number), and many more. Think for example if you need to encrypt birthday field to another birhday that is valid date and lies between 20 and 60 years old and protected from bit flipping. You can easily do that with block cipher with small block size, but you will be unable to satisfy these requirements with stream ciphers. For block ciphers with small block size (such as 40bits or less bits), it is clear that adversary can collect encryptions of all points of the domain. Therefore security goals of the block ciphers with small block size are different than security goals of conventional block ciphers and could be expressed as: even when adversary, having access to encryption oracle, has collected encryption of all but the last two points of the domain, adversary should be unable to distingiush encryption of remaining points significantly better than a random guess.

-Valery.

Reply to
Valery Pryamikov

A one-time pad cannot be broken by brute force.

--
Philip Potter pgp  doc.ic.ac.uk
Reply to
Philip Potter

That doesn't fall within the formal definition of encryption. Can you refine on your comment?

Reply to
Uncle Noah

Please don't quote signatures. They contain information which doesn't need to be repeated in other messages.

Whose formal definition of encryption?

--
Philip Potter pgp  doc.ic.ac.uk
Reply to
Philip Potter

By this do you mean the following: Assuming ECB, for any key, Enc(key,P_i) = Enc(key,P_j) => P_i = P_j ?

But for any block-sized segment, key, of the keystream, Enc(key, P_i) = Enc(key, P_j) => P_i = P_j as 'Enc' is linear, typically XOR.

So stream cyphers are as much PRPs of the set of all blocks as block cyphers are.

Collisions of what?

But on average, 50% of the bits will be left unchanged by encryption in the block cypher case too.

Phil

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

Not yours obviously.

I can see that all crypto guys hate steganography. But traditionally steganographical methods are highly regarded for any serious message hiding. Can't you just consider steganography as another branch of the art of information hiding? Encryption is just one of the branches?

Steganography was really common among agencies, everybody knows that. Some serious documentaries featuring interviews of people involved refer to that.

Kind regards

Reply to
Uncle Noah

Fix block size x and start encrypting values in range {1, ..., 2^x-1}. With block cipher you can encrypt as many values as you want without collisions, and if block cipher is decent, any following encrypted value will be hard to distinguish from value returned by random PRP. With stream cipher - two encryption with the same keystream is enough to recover the keystream. I.e. if you use the same keystream for encrypting all values in {1, ..., 2^x-1} it stops acting as PRP after encryption of two values - any any following encrypted value being trivially distinguishable from random PRP. That also means, that for encrypting values {1,..., 2^x-1} with stream cipher you will be using different keystream (or some key schedule). But this is PRF with collision boundary on 2^x/2 (i.e. expected collision after encryption of values {1,...,2^x/2}).

See above.

distribution of unchanged bits will be close to uniform for a decent cipher (otherwise it is trivially distinguishable from PRP).

-Valery

Reply to
Valery Pryamikov

Duh, when i talk about distinguishability, "random PRP" should read as "random permutation" of course (quite a stupid typo).

-Valery

Reply to
Valery Pryamikov

It would be even better to put it that way - having only one encryption with the stream cipher, any following encryption with same keystream is trivially distinguishable from random permutation. So, stream cipher can never be called PRP.

Using stream cipher with different keystream is PRF - therefore collisions.

-Valery

Reply to
Valery Pryamikov

Quite.

I don't see that. In fact I'm sure people here appreciate steganography for its uses. I quite like the concept of the StegFS steganographic filing system, for example, though I don't use it.

Steganography is good for intelligence agencies, yes. There's a good story about a spy who hid a message in a painting: he encoded morse-code in the lengths of reeds in the landscape.

But I can't see any use for steganography in high-volume, predictable-traffic-pattern communications, as happen in most commercial uses of information hiding. How would you use steganography to protect my confidentiality when details of my banking transactions travel the international banking networks?

On top of that, why use steganography alone? I think you'd be mad to use steganography and not back it up with cryptography.

--
Philip Potter pgp  doc.ic.ac.uk
Reply to
Philip Potter

AFAIK the main high-volume commercial use of steganography is in DRM.

Reply to
Paul Rubin

Also known as "rubber hose codebreaking." tie the fellow with the passphrase up and beat him with a rubber hose until he reveals it. Far easier and cheaper than trying to break AES or even RC4.

In addition, the above claims are false. Steganography is

*not* perfect, even for trusted recipients. A brute force examination of everything that someone sends is far less work than brute force guessing of any but the very shortest of passwords. It is also *not* true that cryptography can always be broken by brute force and it is *not* true that it is only a matter of computational power. A one-time pad cannot be broken by brute force methods, even if the opponent has infinite time and infinite computer resources. (It has other sorts of problems, but being susceptible to a brute force passphrase geussing attack isn't one of them).

To round out this trifecta of flaws, there is a basic problem with using shared passphrase / shared secret key cryptography in embedded systems. Such systems either have the secret key inside the embedded system or they don't. If they do, it is always possible to extract the key. If they don't, the end- user has to enter a key, and somehow you need to get that key to him in a secure manner, so why not use your secure method of sending key information to send whatever it is you are trying to encrypt with your embedded system? Or, why not use your secure method of sending key information to send a one-time pad? That would reduce the complexity of the code in the embedded system to a simple XOR operation.

(These problems with shared secret key cryptography were major drivers behind the development of public key cryptography.)

--
Guy Macon
Reply to
Guy Macon

Yes it does.

------------------------------------------------------

Uncle Noah wrote:

And you can see this...how? See URLs below.

Steganography is simply another tool with its own advantages and disadvantages. It is neither useless (as you are pretending that someone here claims despite no such claim being made) nor is it the perfect magic bullet that you claim it is.

Again, steganography is simply another tool with its own advantages and disadvantages. One of the disadvantages is that it is pretty easy to do a brute-force check of everything sent by a particular person or computer. One of the advantages is that it doesn't attract as much attention to you if nobody knows that you are sending secret information.

Here is the answer to the above, and to all future questions like the above:

formatting link
formatting link
formatting link
formatting link

--
Guy Macon
Reply to
Guy Macon

I'm missing how steganography is used in DRM -- scrambling the information is cryptography, not steganography. Steganography would try to convince you there was no movie on the DVD, not that you couldn't watch it.

Reply to
Joe Pfeiffer

What are your requirements for:

Maximum code size in bytes (please specify CPU)?

Maximum cycles used to encrypt each bit of data?

Maximum RAM used?

Maximum ROM used?

The ratios between the above can vary wildly. I recently designed a product tht had a 1MHz 6502 with 64 bytes of RAM and 512KB of bank-switced masked ROM, so my code and unchanging data tables were pretty much unlimited, CPU cycles were fairly abundant, but RAM was really tight. (It had a huge ROM to hold audio).

--
Guy Macon
Reply to
Guy Macon

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.