| Welcome to Crypto. We hope you enjoy your visit. You're currently viewing our forum as a guest. This means you are limited to certain areas of the board and there are some features you can't use. If you join our community, you'll be able to access member-only sections, and use many member-only features such as customizing your profile, sending personal messages, and voting in polls. Registration is simple, fast, and completely free. Join our community! If you're already a member please log in to your account to access all of our features: |
| My Crypto Idea | |
|---|---|
| Tweet Topic Started: Nov 30 2005, 07:10 PM (861 Views) | |
| HellGauss | Nov 30 2005, 07:10 PM Post #1 |
|
Just registered
![]() ![]() ![]()
|
I want to explain an idea about a new way to do cryptography, without sbox. I explained this idea a few year ago in a newsgroup, but the answer didn't explained exactly why i was wrong. i also think that a forum is more 'user friendly' to do discussion.... i don't like newsgroup, i like forum. The idea is a fast key dependant algorithm. It is know that a good cipher cannot base security about secret of algorithm, but only on secret of the key. So what if we keep secret algorithm? There are a lot of very fast SSE2 cpu function that operates on 128 bits registers, which can be inverted for decrypting. these functions are: - Add function - PADDB/W/D/Q and their inverse PSUBB/W/D/Q PXOR these nine functions may be done between encrypting input (for example in a n*128 bit block cipher), or between input and an external (maybe key dependant) parameter. PADDB/Q/W/D are functons that operate between two 128bit registers, and do a sum mod 2^n for each group of n=8 bit (Byte) or n=16 (Word) or 32 (Doubleword) or 64 (Quadword) Each of these nine functions (4add, 4sub and xor) are 4byte long at machine code. - Shuffle - PSHUFD-PSHUFHW-PSHUFLW these operations, used with opportune arguments, can shuffle a sse2 register bits (for more info see http://www.cs.grinnell.edu/~walker/courses...nstructions.pdf ) in an invertible way. These 3 functions are 5 bytes long - Multiplication - PMULLW. This functions take a 128 sse2 (dest) register and multiply each 16 bits for the corresponding 16 bit of another (source) register. If whe choose source odd for each 16 bit, we can calculate multiplicative inverse of it and create a 128 bit register for decrypting. This multiplicativa parameter can be keydependant. PMULLW instruction is 4 byte long - Shift - With the help of a temp register we can do shift of a 128 register. The instructions are: PSSLW/D/Q, which shift each group of 8 word, 4 doubleword, or 2 quadword by an amount of digit There is also PSSLDQ, which can shift the entire 128 bits (doublequadword) register but only by a multiple of eights (id est, it shift the byte, not the bit) These operations are 18byte long each, since we have to use it twice and do 2 move instruction for temp register (=4 machine operations). I want to underline that the key will not only defines the operands of these instructions, but also the instruction themeselves. For examples if we have to do an add instruction somewhere, we can use 3 bit of the key to specify if we want to do a PSUBB/W/D/Q or PADDB/Q/D/W. Also we can do A LOT of rounds, since operations are EXTREMELY fast. I wrote a program ( http://xoomer.virgilio.it/jbgenov/hgc.cpp ) that encrypt (ECB mode only) with this idea (it works). The problems in that algorithm are (see my cipher before continue reading, there is a detailed description of how it works) 1)operations are mixed in a quite 'random' way (i'm not a cryptographer), so it's probably insecure. 2)The code lenght is not fixed. 3)Since the code length is not fixed, the machinecode-writer algorithm is not well structured and very slow. I think it's better do created a long code string in which change only needed byte. For example 66 0f xx yy means an add operations (xx specify which of the 9 kinds of adds) between 2 operand (specified by yy) What do you think of this idea? PS i'm VERY SORRY for my bad english.... [edit] oops there is a little errore in the source code... i forgot to put comments on some useless lines..... now it's ok you need a comiler with intel asm sintax to build exe |
![]() |
|
| rot13 | Nov 30 2005, 08:36 PM Post #2 |
|
Elite member
![]() ![]() ![]() ![]() ![]() ![]() ![]()
|
I can't offer you much in terms of a detailed analysis. I did read the comments on sci.crypt and I see that the discussion got sidetracked pretty quickly. The first response, though, points to the difficultly with your algorithm, in that the security of the algorithm various widely depending on the key selection. Because you basically have a different algorithm for each key, it is not easy to tell when choosing a key whether it will be a safe key or not. One of the reasons they cryptographers are always talking about making the algorithm public is that you want some reasonable assurance that the algorithm is safe. If a lot of qualified people have tried to break it and have failed, you have at least a reasonable assurance that it is a safe algorithm. If the algorithm changes with each key, how can you be sure that it isn't easy to break? Nobody has the time to do an analysis on every key to make sure it is okay. You yourself admit that you can't tell how secure it is, and I'm not very good with digital cryptograph either, so I can't tell either. I think it is difficult for almost anyone to determine how secure it is precisely because there is no single algorithm. |
![]() |
|
| insecure | Nov 30 2005, 09:08 PM Post #3 |
|
NSA worthy
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]()
|
The difficulty of analysis is of course one problem, as you rightly point out. Here are some others: 1) you don't actually gain anything from using 2N different algorithms that you wouldn't gain far more easily from having N extra bits in your key. 2) it may well be that the algorithms you choose have distinctive frequency characteristics (for example, maybe one algorithm has a tendency to clear bit 19 in each block; maybe another likes the high bit to be set - and so on), which could rapidly lead to a cryppie correctly identifying which algorithm was chosen. In this case, you would actually have been better off with a longer key rather than a hidden algorithm, because you could easily lose that part of the secrecy to no good effect. 3) The problem nowadays isn't to make cryptography more secure, because we already have secure algorithms freely available to us (AES, Twofish, RSA, etc). The problem is one of making algorithms that are not only secure (at least as secure as AES, Twofish, RSA, etc) but also fast and convenient to use. To replace a mere four bits of key, you would have to write sixteen different algorithms, all of which enciphered data amazingly quickly and amazingly securely. It's hard enough writing one! Bottom line - if you want to do it for fun, that's great - feel free. But this idea isn't ever going to rock the world of cryptography on its foundations. By the way, your code didn't compile on my system:
(And looking through the code, I have to say that missing headers were the least of its problems. Sorry.) |
![]() |
|
| Donald | Dec 1 2005, 03:58 AM Post #4 |
|
NSA worthy
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]()
|
My question is: how is this going to hold up against a Known Plaintext attack? How difficult would it be to unwind the operations required to produce a known crypt from a known plain? I suspect it might be quite a bit easier than attempting the same reversal against s boxes. Donald |
![]() |
|
| insecure | Dec 1 2005, 04:05 AM Post #5 |
|
NSA worthy
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]()
|
Yes, I'm afraid you can't really ignore S-boxes if you want decent confusion. The purpose of confusion is to hide the relationship between the ciphertext, the plaintext, and the key. S-boxes do this really, really well, although by themselves they are not enough, of course. |
![]() |
|
| Guest | Dec 1 2005, 08:40 AM Post #6 |
|
Unregistered
|
That header is for low-level IO file functions. I didn't used fopen&co because they don't work with >2^32 byte filesize. I used MS VC 6 (student edition) to compile. gcc doesn't work with intel asm sintax. I'm not familiar with at&t asm sintax used in gcc. About my cipher idea...... Don't focus on my particular implementation of this idea in my code, i want to focus on the idea. It was only a test to see if i was able to dinamically create machine code and to create the inverse decrypting code. the main idea to focus is the encdec function: void encdec (byte* par,byte* code,byte* input,byte* output,unsigned int packnum) { __asm { mov edx,par; movdqu xmm4,[edx]; //mult mov ecx,packnum; mov eax,input; movdqu xmm5,[edx+16]; //xor/add mov ebx,output; movdqu xmm7,[edx+32]; //1 ttt: jecxz esci; movdqu xmm0,[eax]; movdqu xmm1,[eax+16]; add eax,64; movdqu xmm2,[eax-32]; movdqu xmm3,[eax-16]; call code; dec ecx; movdqu [ebx],xmm0; movdqu [ebx+16],xmm1; add ebx,64; movdqu [ebx-32],xmm2; movdqu [ebx-16],xmm3; jmp ttt; esci: } this load 512bit (4registerx128, but can also be 256=128x2), then the 'call' move the instruction pointer to a dinamically created code. when call returns the output is moved in the output buffer. It's EXTREMELY fast. Also code creation (it's an init of the encrypting/decrypting function) is quite fast, and can be faster if we use fixed length code. The block cipher operates only in the cpu register. If we use sbox we have to work with ram, which is VERY slow. What you claim is that these functions (shift/shuffle, multiplication, XOR/additions) are too 'linear' to resist (for example) a choosen plaintext attack. Now let's say that the key k is expanded in two subkey. k1 will define operations to do k2 define some parameters to operate with What you say is: 1) for each k1 exists an attack that break the cipher, for each k2 ok, this is obviously true with those silly linear operation, but in this situation you have to claim that 2)Exists an attack that break the cipher, for each k1 and for each k2. This is a stronger condition It's like the mathematical difference between a continous function and a 'uniform[?? i hope this is the right english word??]' continuos function. The first say that 1)For each epsilon and for each x exists an epsylon that bla bla The second say 2)For each epsilon exists an epsilon that for each x bla bla this is stronger I think the only problem in this cipher idea are a) weak key problem b) linear cryptanalisys maybe both problem can be solved arranging machine operation in a smart way. |
|
|
| HellGauss | Dec 1 2005, 09:20 AM Post #7 |
|
Just registered
![]() ![]() ![]()
|
One note about code creation. Actually, we don't need to write manually each algoritm. We can do it automatically. We have just to define a general algorithm. For example (IT'S JUST AN EXAMPLE): we create 2 key dependant parameter (one for multiplication and one for xor/addition/subtraction) then we do: operation 1) an add instruction between data (3 bits key used, since we can choose in 8 different functions) operation 2) multiply with mult keydependant parameter operation 3) Shuffle (we ca choose a subset of 'good' permutation, and the key will choose which one to use) operation 4)a XOR between the key dependant parameter and data operation 5)A shift (we can choose in a lot of possible (key dependant) shift) operation 6)An addition with external parameter (other 3 bits) Return to operation 1 and do it n times, and for each pair of two 128 register (operation are both between data and between keydependant parameter). Trust me.... we can do a lot of cicles, It's faster than any implementation of AES. to write the machine code (and dec-code) i think the fastest way is create an array with 'machine code structure' in known bytes, and write the key dependant values in the unknow bytes (there are only few key dependants byte, since operations are very similar when written in machine code). For example, to choose one of the add function we have to specify only one byte. To choose a shift we have to specify only two of the 18 bytes: one to select the cpu instruction and one for the amount of shift. |
![]() |
|
| Donald | Dec 1 2005, 02:12 PM Post #8 |
|
NSA worthy
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]()
|
I'm not certain that speed is an issue here. AES already runs so fast that fully encrypted hard drives are practical. The idea is interesting, but I keep coming back to: 1 : even with the best keys it is more linear than modern block ciphers and therefore seems likely to be more vulnerable. 2 : there is no way for the user to know if they picked a good key, or a bad key, and it's inherent in the design that there WILL be bad keys. And problem 2 actually causes several sub problems 2a : The program will have to be smart enough to detect and reject bad keys. That is a difficult AI problem 2b : *IF* you can make the program smart enough to reject bad keys, you have reduced your keyspace. By how much? Who knows, that's back to the 2a problem of how do you detect a bad key. 2c : Every different key creates a different block cipher. Now I realize that is an ADVANTAGE you were aiming at, each cryptographic attack on a new key has to start over new. BUT it's also a major DISADVANTAGE because It's impossible to test this. You would have to test and analyze every single key, because even if cryptanalyst the world over decided that key X was secure, changing one bit in the key produces a new cipher that has not yet ben analyzed and may have a huge gaping hole in it. Which leads us to a conundrum. If you don't analyze every possible key, your cipher isn't secure, if you CAN analyze every key, your cipher isn't secure. This is a very interesting idea, I'm just afraid that it's disadvantages make it unusable as a primary cipher. Now, what you might be able to do with it is use it as a secondary cipher. First run your data through AES, THEN run the final result through your key dependant algo cipher. Now, even if someone manages to crack your cipher, they just have an AES layer that they can't read. AND, cracking the cipher will be much much much more difficult because how do you recognize success? The AES stream should be indistinguishable from random data. Of course, this is rather redundant since AES has resisted all attacks so far, but there are always paranoids out there looking for a second layer of protection. Donald |
![]() |
|
| HellGauss | Dec 1 2005, 03:15 PM Post #9 |
|
Just registered
![]() ![]() ![]()
|
2a i think that the problem is 'the programmer must be smart enough to make each algorithm key-generated not weak (id est, each key is secure)' 2b Same as 2a 2c Not only a new attack must start over new, but also a new attacker 'don't know' were to start, because he don't know what is the background cipher. It's like if i say you to decrypt dsjkhfgbvljhdsbfvjhdsbfvjhbdskfjhvbs knowing that "hello" is crypted in "hjfbjdshbfkjshdbfkjshbfdkjdfsdfsfds", without any other information. May be i use a weak algorithm, but you don't know which one. However i understand what you say. My idea can conduct not to a secure algorithm, but only to an algorithm which we cannot say if it's secure or not, because it is too difficult to analize. NOTE i search internet for other algorithm used..... i found this http://www.mediacrypt.com/_pdf/IDEA_Techni...iption_0105.pdf which not use sboxes (maybe non linearity is provided by mod 2^16+1 multiplication that i think cannot be easily done in cpu. in my algorithm can be used a mod 2^16 multiplication by an odd number, which are 1 cpu instructions, and works on 128 bits. What i have in mind is an algo very similar to 'IDEA', but in which some operations are key dependant. |
![]() |
|
| Donald | Dec 1 2005, 03:28 PM Post #10 |
|
NSA worthy
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]()
|
There is currently an attack that can break IDEA reduced to 5 rounds. The full IDEA is only 8.5 rounds. That seems a bit uncomfortably close for my taste. Attacks always get better, never worse. But at one time IDEA certainly was considered to be one of the best block ciphers around. But it is very specially designed to mix algorithms from different groups. With the key morphing algorithm, we wont have that careful design guaranteeing a secure mixture. Donald |
![]() |
|
| 1 user reading this topic (1 Guest and 0 Anonymous) | |
|
|
| « Previous Topic · Challenges · Next Topic » |





![]](http://z2.ifrm.com/static/1/pip_r.png)




12:26 AM Jul 11