On the next Propeller, it has been said by many, and I totally agree, that a publicly-defined algorithm should be used to encrypt/decrypt program data, when desired. That way, people can decide for themselves if it is sufficient, and use it if they choose. This keeps the air clear.
Does anyone have an objection to the following encrypt/decrypt algorithm?:
1) Each Propeller chip will have 64 programmable security bits.
2) The customer can set these 64 bits one time to whatever he wants, then they cannot be changed.
3) These bits are readable after a reset by the permanent ROM code in the chip.
4) Once read, the 64 bits become hidden until another reset.
5) The bits' values are used by the ROM code for decrypting host-downloaded or external-EEPROM code.
6) The ROM code is in the main memory and can be read by anyone - no secrets about what it does.
7) Encryption is done on the host side, before downloading, using the 64-bit key.
8) Thirty-two of the 64 bits are used to mux one-of-two unique LFSR tap sets for 32 different 32-bit LFSRs.
9) The other 32 bits are used to initialize the LFSRs.
10) For each long needing decryption, the following is then performed:
----a) All 32 LFSRs are each cycled 32 times.
----b) All 32 LFSRs' new values are XOR'd into the encrypted long in order to decrypt it.
Authentication is afforded by downloading pre-encrypted code, then making sure the decrypted plaincode has proper checksums.
A customer can pick a 64-bit code for a product of his, and then send out secure field upgrades.
So, does anyone think this would be a poor approach? Why?
Chip, maybe I'm being dense, but are you asking about an algorithm or a key method?
Seems to me you are discussing an algorithm that uses the key to init the LFSRs to a known state, then using XOR encryption to obfuscate the code.
The one thing was thinking of, what happens to the "boot" command that allows you to read in new code and reboot? If the EEPROM is encrypted, this is effectively read once, write many memory.
I had always assumed that a) each chip sold would have a unique serial (like DS has those 1 wire serials) b) the key would be OTP. c) the encryption algorithm would be something like AES-128, since that's already been written for the Prop.
Also, how does your XOR algorithm protect against feeding it a known ROM contents, such as FF... and then using a reset attack or load from PC to puke out it's memory?
Chip, this method precludes us from using these fuse bits for anything else.
So, could 1bit be used to determine if decoding is done and hides the fuse bits if burnt. If not burnt, all bits are visible and no decryption is performed. This would allow us to use the fuse bits as a serial number, etc.
I also think your method could be quite easily attacked by sequential resets. Am I wrong in thinking this?
Is it still going to be possible to boot from SD Card?
Chip, maybe I'm being dense, but are you asking about an algorithm or a key method?
Seems to me you are discussing an algorithm that uses the key to init the LFSRs to a known state, then using XOR encryption to obfuscate the code.
The one thing was thinking of, what happens to the "boot" command that allows you to read in new code and reboot? If the EEPROM is encrypted, this is effectively read once, write many memory.
I had always assumed that a) each chip sold would have a unique serial (like DS has those 1 wire serials) b) the key would be OTP. c) the encryption algorithm would be something like AES-128, since that's already been written for the Prop.
Also, how does your XOR algorithm protect against feeding it a known ROM contents, such as FF... and then using a reset attack or load from PC to puke out it's memory?
Each LFSR would have two possible tap sets. These would be hard-coded in ROM, but selected by security bits. For example, LFSR#0 could use taps $80000057 or $80000414, while LFSR#1 could use taps $80000106 or $800004F3, and so on. It would take 32 security bits to pick all the tap sets. The other 32 bits could be used to initialize the 32 LFSRs. The goal is to make something approaching a one-time-pad that can be used to decrypt executable program code.
Because all encryption is done on the host side, and then downloaded as encrypted code, and then decrypted and checked for valid checksums, you wouldn't be able to fire off a bunch of $FF's and get code to execute. Checksums would fail and nothing would happen. If you did manage to get a valid checksum, chances would be about zero that you had downloaded any meaningful code that could feedback anything to you about what the decryption was. The checksum validation aspect seems, to me, to pose a huge barrier to observing the encrypted-to-decrypted relationship.
As far as numbering goes, I'm thinking of letting the customer handle it, if he chooses to. You can ignore the security bits, if you want, and just download straight. Maybe we could borrow one of the bits to serve as an encrypted-download-only flag, so that all downloads must be encrypted and keyed to that part. That way, nobody could load their own code into your hardware.
Chip, this method precludes us from using these fuse bits for anything else.
So, could 1bit be used to determine if decoding is done and hides the fuse bits if burnt. If not burnt, all bits are visible and no decryption is performed. This would allow us to use the fuse bits as a serial number, etc.
I also think your method could be quite easily attacked by sequential resets. Am I wrong in thinking this?
Is it still going to be possible to boot from SD Card?
We could come up with some simple rules in the ROM code about how the security bits are used (id, optional security, or constant security).
If it takes 1 second to perform a download after reset, before you get any feedback, it would take up to half a trillion years to discover the key.
The decryption could work from host download, EEPROM, or SD card.
I start to worry. I used to have a pile of unusable AVR's on the bench. Unusable because the fuses got blown and either could not be reprogrammed or required a high voltage programmer to resuscitate them, which I never had. Not that I intentionally ever tried to blow the fuses. I would hate to have a pile Props on the bench for which I don't know what ever random key has inadvertently be set in them.
It would be of great use to be able to use those 64 bits as an ID. For example we use such ID's on devices to ensure that only parameter sets for that unit are loaded into it and not confused with parameter sets for other units. If the parameter set has the wrong ID for the unit it is rejected.
So really the question being asked is "how hard is it for this encryption scheme to be broken?". I suspect there are few people in the world skilled and experienced in cipher busting enough to answer that question.
I start to worry. I used to have a pile of unusable AVR's on the bench. Unusable because the fuses got blown and either could not be reprogrammed or required a high voltage programmer to resuscitate them, which I never had. Not that I intentionally ever tried to blow the fuses. I would hate to have a pile Props on the bench for which I don't know what ever random key has inadvertently be set in them.
It would be of great use to be able to use those 64 bits as an ID. For example we use such ID's on devices to ensure that only parameter sets for that unit are loaded into it and not confused with parameter sets for other units. If the parameter set has the wrong ID for the unit it is rejected.
So really the question being asked is "how hard is it for this encryption scheme to be broken?". I suspect there are few people in the world skilled and experienced in cipher busting enough to answer that question.
There is a 65th bit which inhibits further security-bit programming. If you knew that you never wanted your chip to become keyed, you could just blow that 65th bit, leaving the rest at 0's. This would make the chip like the current Propeller.
The ROM code could look at maybe the two top bits and determine what "mode" the chip has been set for.
Yes, I'm wondering if anyone thinks that this idea is unsound. I think there are a few people who'll read this that will have some idea.
Rule number one in the security world is "DO NOT TRY TO INVENT YOUR OWN ENCRYPTION ALGORITHM".
Sorry for shouting but I think it is important. Here is how David Wheeler puts it: "Cryptographic protocols and algorithms are difficult to get right, so do not create your own. Instead, where you can, use protocols and algorithms that are widely-used, heavily analyzed, and accepted as secure. When you must create anything, give the approach wide public review and make sure that professional security analysts examine it for problems. In particular, do not create your own encryption algorithms unless you are an expert in cryptology, know what you're doing, and plan to spend years in professional review of the algorithm. Creating encryption algorithms (that are any good) is a task for experts only."
What is described here with key bits. LFSR's etc is an attempt at inventing an encryption algorithm so I would advise taking the above advice.
Next, from reading around I have learned that often even when I "good" algorithm is taken into use in a system the system ends up getting broken anyway due to bad implementation. Have a google for how WEP was broken due to careless implementation.
Personally I would start by looking at the TEA encryption algorithm. http://143.53.36.235:8080/tea.htm
Then there are derivatives XTEA and XXTEA. Then there is RC4. Or sure there are others.
Given this is going into ROM there must be one of these that fits easily.
Use sha 2 to authenticate a boot loader in eeprom, hashing the secret key with the data and compare witha hash signature in the boot loader code in eeprom. Then the boot loader is trusted and can have the key to decrypt the rest of the eeprom.
Chip has proposed that the decryption algorithm resides in ROM. This need not be the case it could be downloaded with the binary or as a pre-load stage. This would allow that when the encryption scheme is broken (cipher algorithm or implementation mistake) it would be possible to adopt a new algorithm without having to remask the chip.
However this requires that the decryption phase, now using downloaded code, can be trusted not to reveal the key bits. At this point we need a signed decryptor/loader that won't run unless the ROM code authenticates it.
Heater, that TEA algorithm would be way faster and pretty compact, too. I'm going to try to get a handle on it.
The thing that seems strange to me is that it uses a 128-bit key to process 64 bits at a time, without any regenerative feedback from run to run. I guess that's why it's called a block cipher. Seems almost simplistic, but I trust that it's strong. I could make an instruction to do that job!
With the few exceptions mentioned in section 3.8, this research concludes TEA as a
best fit cryptographic algorithm for small devices where memory and power are primary
concern.
Now, most people would take the C version of the algorithm to start from. But not Chip he starts from the x86 assembler version:)
Sorry I edited my post, Heater. I thought that code without formatting would just give people a headache. I agree that, upon discovery, the C is much simpler:
void encipher(unsigned long *const v,unsigned long *const w,
const unsigned long *const k)
{
register unsigned long y=v[0],z=v[1],sum=0,delta=0x9E3779B9,
a=k[0],b=k[1],c=k[2],d=k[3],n=32;
while(n-->0)
{
sum += delta;
y += (z << 4)+a ^ z+sum ^ (z >> 5)+b;
z += (y << 4)+c ^ y+sum ^ (y >> 5)+d;
}
w[0]=y; w[1]=z;
}
void decipher(unsigned long *const v,unsigned long *const w,
const unsigned long *const k)
{
register unsigned long y=v[0],z=v[1],sum=0xC6EF3720,
delta=0x9E3779B9,a=k[0],b=k[1],
c=k[2],d=k[3],n=32;
/* sum = delta<<5, in general sum = delta * n */
while(n-->0)
{
z -= (y << 4)+c ^ y+sum ^ (y >> 5)+d;
y -= (z << 4)+a ^ z+sum ^ (z >> 5)+b;
sum -= delta;
}
I have it on good Authority that Chip has decreed that the new chip be known simply as "Bob".
Absolutely! The three Bobs in my household vote yes. (My BoeBot named Bob, my peecee named Bob and my dungeon wandering Arch-Mage... Bob.) Of course my iMac called Irving abstains from the voting!
Chip, I'll second Heater's comments: good crypto is hard to get right and bad crypto is effectively the same as no crypto. Your LSFR scheme might be sufficient for protecting your IP, but you are trying to sell this to customers to protect their IP. Using an identifiable encryption algorithm should also be a selling point.
I recognize that AES-128 may be too slow for your purposes, but there are other proven algorithms out there which may be faster / smaller / easier to implement.
Some other items:
1. For many crypto algorithms both the initialization vector and the private key need to be secured. A known initialization vector may be as bad as a known private key.
2. It should not be possible to reset the secure storage once it has been programmed. Otherwise an attacker could replace the EEPROM with their own.
3. Whatever algorithm you use (both the base algorithm and any chaining) should protect against known plaintext attacks. This is especially true because the first block of a Propeller binary is somewhat static and thus should be considered known.
1. What do you mean by the initialization vector as opposed to the private key.
2. Could you elaborate on that?
3. I guess there should be some random "salt" added to the start of the binary prior to encryption on the host which ensures that the same start up code or whatever is not encrypted the same way in every program a user produces. (assuming they are using the same key all the time, might not be required if they do not).
1. What do you mean by the initialization vector as opposed to the private key.
2. Could you elaborate on that?
3. I guess there should be some random "salt" added to the start of the binary prior to encryption on the host which ensures that the same start up code or whatever is not encrypted the same way in every program a user produces. (assuming they are using the same key all the time, might not be required if they do not).
1. The initialization vector is a kind of "initial state" for the encryption decryption. It's more important for block chaining modes where the ciphertext from one block is used as the IV for the next block to add entropy, so the IV is required to provide that entropy to the first block. See http://en.wikipedia.org/wiki/Initialization_vector
2. Imagine you have a Prop2 product which implements a critical process (like a centrifuge used to enrich uranium). If it were possible to reset the private key, then it would be possible to reprogram the device to not perform as expected (e.g. Stuxnet). Note: it should be possible for the programmer to set the key & IV so multiple Prop2s may use the same encrypted binary and so the EEPROM may be updated after the Prop2 is programmed.
3. The IV takes care of the randomization, but that may not protect against known plaintext attacks. The trick with the Propeller is the first n bytes are effectively static and are therefore vulnerable. One solution would be to fill unused RAM (or at least the last block) with random data then encrypt the binary in reverse order. However, I don't know if applications assume unused memory is set to a known value (i.e. zero).
In general aviation a Turbo Prop is almost at the top of the pack, something most weekend warriors dream
about flying. I think it is a good name for the new chip ...
I have been pondering on the fact that the current prop has an approximately fixed set of 16 bytes, so I have some ideas based on presumptions which may be wrong.
Assumptions...
The ROM is 2KB PASM and is loaded into cog 0 upon reset where it executes
It does not mandate that any specif code be present in hub ram.
Concept....
Code to be loaded is stored in data blocks of 512 bytes, including...
A 4 byte (32bit) header address for the hub location (18 bits used if 192KB prop and the other bits are don't care and are set by random by the encryption)
504 bytes of data
A 4 byte (32bit) trailing checksum
Loading...
The cog determines whether to download, load from eeprom, or load from SD card
The cog now reads the fuses once (and then the fuses cannot be read again until the next reset)
The cog now reads in 512 bytes of data, decrypts, and validates the checksum
If everything is ok, then the cog loads the 508 bytes into hub ram at the address specified. If a failure, go to step 6
The cog repeats the loop at step 3
Here for a checksum failure. The cog performs one more decryption on the first 4 bytes and if the checksum matches goto step 8, else step 7
An invalid load so the prop executes a random delay loop > 5 secs (to prevent someone trying to break the prop decryption) and then stops
If bit ? of the fuse bits is set, then the location holding a copy of the fuse bits is reset. Alternately, if bit ? is not set, then a copy of the fuse bits is copied to??? for use later by the user. This would allow other uses for the fuse bits.
The cog performs a new coginit for cog 0 using the double decrypted first 4 bytes as the start hub address. (the remaining data is discarded)
The checksum failure would be the start record. The remaining data would be randomly generated by encryption.
Advantages...
The code can be loaded out of sequence, thereby thwarting any known hub data pattern, such as the first 16 bytes.
The user can actually perform his own algorithm as well, including setting up the first 16 bytes if required.
Question
Can we have pasm access to the decryption instruction(s) ? They could be useful for other forms of downloading.
I would much rather see a "this is encrypted" bit in the downloaded code than to have a bit in ROM that requires subsequent downloads to be encrypted. That way the same part could load and run both encrypted and unencrypted code. I also agree wholeheartedly with Heater's admonition not to try inventing your own encryption algorithm. It's much too easy to fool yourself into thinking something is secure when it isn't.
I would much rather see a "this is encrypted" bit in the downloaded code than to have a bit in ROM that requires subsequent downloads to be encrypted. That way the same part could load and run both encrypted and unencrypted code. I also agree wholeheartedly with Heater's admonition not to try inventing your own encryption algorithm. It's much too easy to fool yourself into thinking something is secure when it isn't.
-Phil
Thanks, Everyone, for all your ideas!
Phil, imagine you've built a gadget for which you don't want people to download anything but authenticated code. Maybe the processor is even potted, so they can't just solder on another chip. In a case like this, you'd want the chip to only accept valid code from you. Programming that mode permanently would be something you'd do when you build the product. If you knew you'd never want that mode for that chip, you'd just freeze all the bits at zero, so they could not be altered, keeping the chip in Free Willy mode. Encryption would pose some extra responsibilities on the part of the user, like remembering the key. You could make a run of the same product with a constant key, making field upgrades possible for that product without consideration of the individual units.
I like the idea someone had for having blocks downloaded out-of-order. That would take care of any static header weakness. And using the last results to alter the key for the next block is neat.
Read first 32-bit word from flash, use as length. Read <x> bytes from flash (including length descr). Verify signature using public key stored in fuse bits. If signature fails, halt. If signature succeeds, load into hub ram, load first 504 longs into cog, and run.
This way, you could load a verified bootloader from flash, which would then perform any further encryption/decryption necessary. You could also load a verified bootloader into flash that does no encryption to make development easier. Once development is done, sign a cryptographic bootloader with the private key that matches the public key in the fuse bits.
This way, you support bootloader updates in-the-field, the fuse bits can stay visible all the time, and you only need to worry about people cracking into your development house and getting the private key there.
Phil, imagine you've built a gadget for which you don't want people to download anything but authenticated code. Maybe the processor is even potted, so they can't just solder on another chip. In a case like this, you'd want the chip to only accept valid code from you. Programming that mode permanently would be something you'd do when you build the product. If you knew you'd never want that mode for that chip, you'd just freeze all the bits at zero, so they could not be altered, keeping the chip in Free Willy mode. Encryption would pose some extra responsibilities on the part of the user, like remembering the key. You could make a run of the same product with a constant key, making field upgrades possible for that product without consideration of the individual units.
I like the idea someone had for having blocks downloaded out-of-order. That would take care of any static header weakness. And using the last results to alter the key for the next block is neat.
This sure sounds like trying to keep the whole device secure when an attacker has physical access. This is where I draw the lines for diminishing returns. Phill's suggestion of a "this is encrypted" bit on download should still keep the encrypted code safe, but allow users of a product to re-use it if they're willing to erase the stock code. Ultimately, this is likely to result in a more secure product because people who just want to hack a nifty device that uses a propeller chip won't have to crack the code protection to do it. (see the Playstation 3 and the whole Linux "other OS" mess.)
One more thing that may be useful, would be to have an output pin that is high or low depending on the state of encryption. That way, end-users could modify a device to their liking, but the device could have a warning light in it so that homebrew firmware can't be loaded on a device, which is then sold listed in as-new condition.
Phil, imagine you've built a gadget for which you don't want people to download anything but authenticated code.
That runs so against the grain that it's beyond my imagining.
But I suppose there are paranoid types out there who -- let's say for safety reasons -- don't want someone messing with the code in their device. So how about a two-tiered lockdown: one that pays attention to a "this is encrypted" bit in the downloaded code and one that assumes everything has to be encrypted.
Chip,
The XXTEA algorithm fixes some of the problems in original TEA and is equally as easy to implement. The only know weakness in the XXTEA algorithm involves encrypting a ridiculous number of chosen plain-texts with the unknown key. The only way that could happen is if the entity holding the key encrypts large quantities of someone else's data using the same key that they are using in the Propeller application. I would also recommend 128 bits for the key, since 64 bits may be easy to brute force before the next Propeller reaches the end of its lifetime.
Comments
Is that a banana in your hat, or are you just happy to see me?
On the next Propeller, it has been said by many, and I totally agree, that a publicly-defined algorithm should be used to encrypt/decrypt program data, when desired. That way, people can decide for themselves if it is sufficient, and use it if they choose. This keeps the air clear.
Does anyone have an objection to the following encrypt/decrypt algorithm?:
1) Each Propeller chip will have 64 programmable security bits.
2) The customer can set these 64 bits one time to whatever he wants, then they cannot be changed.
3) These bits are readable after a reset by the permanent ROM code in the chip.
4) Once read, the 64 bits become hidden until another reset.
5) The bits' values are used by the ROM code for decrypting host-downloaded or external-EEPROM code.
6) The ROM code is in the main memory and can be read by anyone - no secrets about what it does.
7) Encryption is done on the host side, before downloading, using the 64-bit key.
8) Thirty-two of the 64 bits are used to mux one-of-two unique LFSR tap sets for 32 different 32-bit LFSRs.
9) The other 32 bits are used to initialize the LFSRs.
10) For each long needing decryption, the following is then performed:
----a) All 32 LFSRs are each cycled 32 times.
----b) All 32 LFSRs' new values are XOR'd into the encrypted long in order to decrypt it.
Authentication is afforded by downloading pre-encrypted code, then making sure the decrypted plaincode has proper checksums.
A customer can pick a 64-bit code for a product of his, and then send out secure field upgrades.
So, does anyone think this would be a poor approach? Why?
Seems to me you are discussing an algorithm that uses the key to init the LFSRs to a known state, then using XOR encryption to obfuscate the code.
The one thing was thinking of, what happens to the "boot" command that allows you to read in new code and reboot? If the EEPROM is encrypted, this is effectively read once, write many memory.
I had always assumed that a) each chip sold would have a unique serial (like DS has those 1 wire serials) b) the key would be OTP. c) the encryption algorithm would be something like AES-128, since that's already been written for the Prop.
Also, how does your XOR algorithm protect against feeding it a known ROM contents, such as FF... and then using a reset attack or load from PC to puke out it's memory?
So, could 1bit be used to determine if decoding is done and hides the fuse bits if burnt. If not burnt, all bits are visible and no decryption is performed. This would allow us to use the fuse bits as a serial number, etc.
I also think your method could be quite easily attacked by sequential resets. Am I wrong in thinking this?
Is it still going to be possible to boot from SD Card?
Each LFSR would have two possible tap sets. These would be hard-coded in ROM, but selected by security bits. For example, LFSR#0 could use taps $80000057 or $80000414, while LFSR#1 could use taps $80000106 or $800004F3, and so on. It would take 32 security bits to pick all the tap sets. The other 32 bits could be used to initialize the 32 LFSRs. The goal is to make something approaching a one-time-pad that can be used to decrypt executable program code.
Because all encryption is done on the host side, and then downloaded as encrypted code, and then decrypted and checked for valid checksums, you wouldn't be able to fire off a bunch of $FF's and get code to execute. Checksums would fail and nothing would happen. If you did manage to get a valid checksum, chances would be about zero that you had downloaded any meaningful code that could feedback anything to you about what the decryption was. The checksum validation aspect seems, to me, to pose a huge barrier to observing the encrypted-to-decrypted relationship.
As far as numbering goes, I'm thinking of letting the customer handle it, if he chooses to. You can ignore the security bits, if you want, and just download straight. Maybe we could borrow one of the bits to serve as an encrypted-download-only flag, so that all downloads must be encrypted and keyed to that part. That way, nobody could load their own code into your hardware.
We could come up with some simple rules in the ROM code about how the security bits are used (id, optional security, or constant security).
If it takes 1 second to perform a download after reset, before you get any feedback, it would take up to half a trillion years to discover the key.
The decryption could work from host download, EEPROM, or SD card.
It would be of great use to be able to use those 64 bits as an ID. For example we use such ID's on devices to ensure that only parameter sets for that unit are loaded into it and not confused with parameter sets for other units. If the parameter set has the wrong ID for the unit it is rejected.
So really the question being asked is "how hard is it for this encryption scheme to be broken?". I suspect there are few people in the world skilled and experienced in cipher busting enough to answer that question.
There is a 65th bit which inhibits further security-bit programming. If you knew that you never wanted your chip to become keyed, you could just blow that 65th bit, leaving the rest at 0's. This would make the chip like the current Propeller.
The ROM code could look at maybe the two top bits and determine what "mode" the chip has been set for.
Yes, I'm wondering if anyone thinks that this idea is unsound. I think there are a few people who'll read this that will have some idea.
Rule number one in the security world is "DO NOT TRY TO INVENT YOUR OWN ENCRYPTION ALGORITHM".
Sorry for shouting but I think it is important. Here is how David Wheeler puts it: "Cryptographic protocols and algorithms are difficult to get right, so do not create your own. Instead, where you can, use protocols and algorithms that are widely-used, heavily analyzed, and accepted as secure. When you must create anything, give the approach wide public review and make sure that professional security analysts examine it for problems. In particular, do not create your own encryption algorithms unless you are an expert in cryptology, know what you're doing, and plan to spend years in professional review of the algorithm. Creating encryption algorithms (that are any good) is a task for experts only."
Ref: http://www.dwheeler.com/secure-programs/Secure-Programs-HOWTO/crypto.html
What is described here with key bits. LFSR's etc is an attempt at inventing an encryption algorithm so I would advise taking the above advice.
Next, from reading around I have learned that often even when I "good" algorithm is taken into use in a system the system ends up getting broken anyway due to bad implementation. Have a google for how WEP was broken due to careless implementation.
Personally I would start by looking at the TEA encryption algorithm. http://143.53.36.235:8080/tea.htm
Then there are derivatives XTEA and XXTEA. Then there is RC4. Or sure there are others.
Given this is going into ROM there must be one of these that fits easily.
Chip has proposed that the decryption algorithm resides in ROM. This need not be the case it could be downloaded with the binary or as a pre-load stage. This would allow that when the encryption scheme is broken (cipher algorithm or implementation mistake) it would be possible to adopt a new algorithm without having to remask the chip.
However this requires that the decryption phase, now using downloaded code, can be trusted not to reveal the key bits. At this point we need a signed decryptor/loader that won't run unless the ROM code authenticates it.
The thing that seems strange to me is that it uses a 128-bit key to process 64 bits at a time, without any regenerative feedback from run to run. I guess that's why it's called a block cipher. Seems almost simplistic, but I trust that it's strong. I could make an instruction to do that job!
Ah, now I see you have edited your post and removed the x86 code.
Wow!.
Check out the cryptanalysis here:
http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=6&ved=0CEkQFjAF&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.93.5394%26rep%3Drep1%26type%3Dpdf&ei=vwc1T4W-HMen4gSmosj8AQ&usg=AFQjCNHyjmZF5YOwWzpJyYx1JAs08CbYBw&sig2=VKWRMT_e3WrDorZVZGNi0Q
Which has the following conclusion:
But TEA or XTEA or XXTEA?
Sorry I edited my post, Heater. I thought that code without formatting would just give people a headache. I agree that, upon discovery, the C is much simpler:
void encipher(unsigned long *const v,unsigned long *const w,
const unsigned long *const k)
{
register unsigned long y=v[0],z=v[1],sum=0,delta=0x9E3779B9,
a=k[0],b=k[1],c=k[2],d=k[3],n=32;
while(n-->0)
{
sum += delta;
y += (z << 4)+a ^ z+sum ^ (z >> 5)+b;
z += (y << 4)+c ^ y+sum ^ (y >> 5)+d;
}
w[0]=y; w[1]=z;
}
void decipher(unsigned long *const v,unsigned long *const w,
const unsigned long *const k)
{
register unsigned long y=v[0],z=v[1],sum=0xC6EF3720,
delta=0x9E3779B9,a=k[0],b=k[1],
c=k[2],d=k[3],n=32;
/* sum = delta<<5, in general sum = delta * n */
while(n-->0)
{
z -= (y << 4)+c ^ y+sum ^ (y >> 5)+d;
y -= (z << 4)+a ^ z+sum ^ (z >> 5)+b;
sum -= delta;
}
w[0]=y; w[1]=z;
}
Absolutely! The three Bobs in my household vote yes. (My BoeBot named Bob, my peecee named Bob and my dungeon wandering Arch-Mage... Bob.) Of course my iMac called Irving abstains from the voting!
Amanda
I recognize that AES-128 may be too slow for your purposes, but there are other proven algorithms out there which may be faster / smaller / easier to implement.
Some other items:
1. For many crypto algorithms both the initialization vector and the private key need to be secured. A known initialization vector may be as bad as a known private key.
2. It should not be possible to reset the secure storage once it has been programmed. Otherwise an attacker could replace the EEPROM with their own.
3. Whatever algorithm you use (both the base algorithm and any chaining) should protect against known plaintext attacks. This is especially true because the first block of a Propeller binary is somewhat static and thus should be considered known.
I don't know much about crypto so:
1. What do you mean by the initialization vector as opposed to the private key.
2. Could you elaborate on that?
3. I guess there should be some random "salt" added to the start of the binary prior to encryption on the host which ensures that the same start up code or whatever is not encrypted the same way in every program a user produces. (assuming they are using the same key all the time, might not be required if they do not).
2. Imagine you have a Prop2 product which implements a critical process (like a centrifuge used to enrich uranium). If it were possible to reset the private key, then it would be possible to reprogram the device to not perform as expected (e.g. Stuxnet). Note: it should be possible for the programmer to set the key & IV so multiple Prop2s may use the same encrypted binary and so the EEPROM may be updated after the Prop2 is programmed.
3. The IV takes care of the randomization, but that may not protect against known plaintext attacks. The trick with the Propeller is the first n bytes are effectively static and are therefore vulnerable. One solution would be to fill unused RAM (or at least the last block) with random data then encrypt the binary in reverse order. However, I don't know if applications assume unused memory is set to a known value (i.e. zero).
They exploited the use of a known set of of 3 chars (wheater reports), repeated twice.
about flying. I think it is a good name for the new chip
Assumptions...
- The ROM is 2KB PASM and is loaded into cog 0 upon reset where it executes
- It does not mandate that any specif code be present in hub ram.
Concept....- Code to be loaded is stored in data blocks of 512 bytes, including...
- A 4 byte (32bit) header address for the hub location (18 bits used if 192KB prop and the other bits are don't care and are set by random by the encryption)
- 504 bytes of data
- A 4 byte (32bit) trailing checksum
Loading...- The cog determines whether to download, load from eeprom, or load from SD card
- The cog now reads the fuses once (and then the fuses cannot be read again until the next reset)
- The cog now reads in 512 bytes of data, decrypts, and validates the checksum
- If everything is ok, then the cog loads the 508 bytes into hub ram at the address specified. If a failure, go to step 6
- The cog repeats the loop at step 3
- Here for a checksum failure. The cog performs one more decryption on the first 4 bytes and if the checksum matches goto step 8, else step 7
- An invalid load so the prop executes a random delay loop > 5 secs (to prevent someone trying to break the prop decryption) and then stops
- If bit ? of the fuse bits is set, then the location holding a copy of the fuse bits is reset. Alternately, if bit ? is not set, then a copy of the fuse bits is copied to??? for use later by the user. This would allow other uses for the fuse bits.
- The cog performs a new coginit for cog 0 using the double decrypted first 4 bytes as the start hub address. (the remaining data is discarded)
The checksum failure would be the start record. The remaining data would be randomly generated by encryption.Advantages...
- The code can be loaded out of sequence, thereby thwarting any known hub data pattern, such as the first 16 bytes.
- The user can actually perform his own algorithm as well, including setting up the first 16 bytes if required.
QuestionCan we have pasm access to the decryption instruction(s) ? They could be useful for other forms of downloading.
-Phil
Thanks, Everyone, for all your ideas!
Phil, imagine you've built a gadget for which you don't want people to download anything but authenticated code. Maybe the processor is even potted, so they can't just solder on another chip. In a case like this, you'd want the chip to only accept valid code from you. Programming that mode permanently would be something you'd do when you build the product. If you knew you'd never want that mode for that chip, you'd just freeze all the bits at zero, so they could not be altered, keeping the chip in Free Willy mode. Encryption would pose some extra responsibilities on the part of the user, like remembering the key. You could make a run of the same product with a constant key, making field upgrades possible for that product without consideration of the individual units.
I like the idea someone had for having blocks downloaded out-of-order. That would take care of any static header weakness. And using the last results to alter the key for the next block is neat.
Read first 32-bit word from flash, use as length. Read <x> bytes from flash (including length descr). Verify signature using public key stored in fuse bits. If signature fails, halt. If signature succeeds, load into hub ram, load first 504 longs into cog, and run.
This way, you could load a verified bootloader from flash, which would then perform any further encryption/decryption necessary. You could also load a verified bootloader into flash that does no encryption to make development easier. Once development is done, sign a cryptographic bootloader with the private key that matches the public key in the fuse bits.
This way, you support bootloader updates in-the-field, the fuse bits can stay visible all the time, and you only need to worry about people cracking into your development house and getting the private key there.
This sure sounds like trying to keep the whole device secure when an attacker has physical access. This is where I draw the lines for diminishing returns. Phill's suggestion of a "this is encrypted" bit on download should still keep the encrypted code safe, but allow users of a product to re-use it if they're willing to erase the stock code. Ultimately, this is likely to result in a more secure product because people who just want to hack a nifty device that uses a propeller chip won't have to crack the code protection to do it. (see the Playstation 3 and the whole Linux "other OS" mess.)
Lawson
But I suppose there are paranoid types out there who -- let's say for safety reasons -- don't want someone messing with the code in their device. So how about a two-tiered lockdown: one that pays attention to a "this is encrypted" bit in the downloaded code and one that assumes everything has to be encrypted.
-Phil
The XXTEA algorithm fixes some of the problems in original TEA and is equally as easy to implement. The only know weakness in the XXTEA algorithm involves encrypting a ridiculous number of chosen plain-texts with the unknown key. The only way that could happen is if the entity holding the key encrypts large quantities of someone else's data using the same key that they are using in the Propeller application. I would also recommend 128 bits for the key, since 64 bits may be easy to brute force before the next Propeller reaches the end of its lifetime.
— David Carrier