Anyone see any vulnerabilities with this algorithm?
Page 1 of 3 123 LastLast
Results 1 to 10 of 23

Thread: Anyone see any vulnerabilities with this algorithm?

  1. #1
    Senior Member
    Join Date
    Jan 2004
    Location
    Hawaii
    Posts
    351

    Post Anyone see any vulnerabilities with this algorithm?

    // f_skaencrypt.h
    // by AxessTerminated
    /*
    approximately two minutes of CPU time for encrypt/decrypt of a
    101,891KB file on a ~299Mhz PII.
    */

    #include <fstream.h>

    void encrypt(char *filein, char *fileout, long key, long key2); //encryption routine
    void decrypt(char *filein, char *fileout, long key, long key2); //decryption routine
    char ch;
    char ch2;

    void encrypt(char *filein, char *fileout, long key, long key2)
    {
    ifstream in(filein, ios::binary);
    ofstream out(fileout, ios::trunc | ios::binary);

    srand(key);
    key = rand() * key2 + 3;
    srand(key2);
    key2 = rand();

    while(!in.eof())
    {
    in.get(ch);
    ch += key;
    ch += key2 * key;
    in.get(ch);
    ch2 -= key;
    ch2 -= key2 * key;
    out.put(ch2);
    out.put(ch);
    }

    in.close();
    out.close();
    exit(0);
    }

    void decrypt(char *filein, char *fileout, long key, long key2)
    {
    ifstream in(filein, ios::binary);
    ofstream out(fileout, ios::trunc | ios::binary);

    srand(key);
    key = rand() * key2 + 3;
    srand(key2);
    key2 = rand();

    while(!in.eof())
    {
    in.get(ch2);
    ch2 -= key2 * key;
    ch2 -= key;
    in.get(ch);
    ch += key2 * key;
    ch += key;
    out.put(ch);
    out.put(ch2);
    }

    in.close();
    out.close();
    exit(0);
    }

    Anyone see how an encrypted file could possibly be cracked? I'm also working on a VC++ version that has 3 keys, and also will allow you to use a file as a key.
    Geek isn't just a four-letter word; it's a six-figure income.

  2. #2
    The Iceman Cometh
    Join Date
    Aug 2001
    Posts
    1,209
    Well, anything that's encrypted, can be decrypted. You've proved that by writing a decrypt function. Based upon that, someone will technically be able to "crack" it. It's also not exactly the most complex encryption algorithm, if that makes any difference.

    Also, a tip. If you're trying to write a solid encryption program, posting it in a public forum isn't exactly the best idea. :-P

    AJ

  3. #3
    Senior Member
    Join Date
    Jan 2004
    Location
    Hawaii
    Posts
    351
    I was planning on making this open source anyways. I'm just a beginner. I know that it's not very great, but aside from the fact that I don't have "security by obscurity", anything wrong with the code itself that would make this exceptionally easy to crack?

    A_T
    Geek isn't just a four-letter word; it's a six-figure income.

  4. #4
    The Iceman Cometh
    Join Date
    Aug 2001
    Posts
    1,209
    Not that I can see. Any sort of encryption algorithm, regardless of how simple or how complex will always have a way to crack it. Since you're using keys (which I'm assuming you would provide to whoever needs to decrypt it) makes it more difficult than one where you don't (which uses a hard-coded key rather than a unique key). I personally don't see any problems with it (besides some out-dated programming techniques), but I haven't written an encryption or decryption program in a couple years.

    AJ

  5. #5
    Old-Fogey:Addicts founder Terr's Avatar
    Join Date
    Aug 2001
    Location
    Seattle, WA
    Posts
    2,007
    I'm not really qualified to evaluate it myself. I think most algorithms in popular use nowadays are popular because of a mix of implementation ease, computational/speed demands, and susceptibility to cryptographic analysis and attacks beyond quasi-linear brute force.

    If it's in your library, you might want to look at "Decrypted secrets : methods and maxims of cryptology" (by Bauer, Friedrich Ludwig) . Some of the math terminology put me off, but there's also some history to illustrate the crypto topics, much of it from WWII. Also there are pointers as to what protocol you should follow with messages sent via the encrypted line, and how certain habits or message structure can provide chinks in algorithms.
    [HvC]Terr: L33T Technical Proficiency

  6. #6
    Senior Member
    Join Date
    Oct 2001
    Posts
    786
    Note: I am not a professional in cryptography. I'm just a senior in high school who likes math

    In short, yes.


    Your random seeding and such takes values that are 2^32 in size, and gives you a number that is 2^15 in size. Try it out for yourself, write a program that seeds the random number generator with every value from LONG_MIN to LONG_MAX. It should print the random number to the screen. Let the program run for a few days, and try to recall if any output exceeded 32768. I seriously doubt it will, because I wrote a program and let it go through about a million combinations before I found a distinct pattern in what rand() produces for each incremental seed.

    So, we know for sure that key2 is between 0 and 32768. If we enthuastically hope that key1 can still be any value between LONG_MIN and LONG_MAX, we might have a total of 2^47 possible combinations (140737488355328 combinations).


    I am thinking there is other stuff that is wrong, but it is all theory at this point in time. But I think that so far I've proved that there is a huge issue in the current algorithm that some serious thought is needed to make it more secure. I am not a vetran in crypto, but I'm sure if it was under any serious scruitny it would crumble from not having a large enough keyspace, among other things that I can't quite explain sanely...


    For my benefit, I will begin to think about things like school. And how I don't have any school supplies yet... Pranks aren't possible with supplies... *whistle* Later.

  7. #7
    Senior Member
    Join Date
    Jan 2004
    Location
    Hawaii
    Posts
    351
    Tim_Axe, that is a very good explanation, thanks. I was going to use __int64 for the keys, but it seems to give me problems when i try using it. I use Dev-C++, that supports __int64 natively.
    Geek isn't just a four-letter word; it's a six-figure income.

  8. #8
    Senior Member
    Join Date
    Nov 2003
    Posts
    107
    Okay, I'm no professional cryptographer, but, I've done my fair share of crypto work and i'm a math geek.

    After looking over the algorithm a bit, i managed to somewhat simplify it and explain it. First off, whever you have ch+=key2*key;ch+=key; you can simplify that to ch+=(key2+1)*key. Now, I'm not up to par on C++, but, I'm pretty sure that when you add a long to a char, it stays within the char's domain (0-255). So, add a % 256 into that then. You also flip-flop the two characters you're working with in the output file. So, a simplified pseudo-code version of the algorithm would be:

    encrypt:
    get 2 characters
    character 1 = (character 1 + (key2+1) * key) % 256
    character 2 = (character 2 - (key2+1) * key) % 256
    exchange characters
    write to file

    decrypt:
    get 2 characters
    character 1 = (character 1 - (key2+1) * key) % 256
    character 2 = (character 2 + (key2+1) * key) % 256
    exchange characters
    write to file

    Okay, now that we've got what's going on laid out pretty plainly, we can start to decide how we want to crack the system. Well, as I look at it, I see that the file which once was something like:

    1234567890

    is now

    2143658709

    So, my first step would be to just put the characters back in order to simplify life. From there, I'd see that all the odd characters had something added to them and all the even ones had something subtracted from them. So, I split the file into separate files, one containing all the even characters, one containing all the odd characters. Then, I'd do frequency analysis of it, hoping for some kind of recognizable pattern. If there was a recognizable pattern, I could start mapping certain characters to others, which would then give me a list of possible keys. For example, if I can tell that the character 'e' has been mapped to 'f', that's a single unit of difference. Let's say it was in the odd set, which i know had things added to it. The keys could be represented by:

    256^n+1

    Where n can be any whole number from 0 to log(32768)/log(256) (read that as log base 256 of 32768, it'll make more sense). Now, I KNOW that the same key was used to encode each character in the odd set. So, as I find other mappings, I can deduce the actual key. HOWEVER, I don't think it's actually necessary to. Since the key 1 will encode the set the same way a key of 257 will, there's really no sense in checking for keys that are greater than 255 (256 maps to 0, remember?).

    Note that when I'm referring to key, I'm referring to the (key2+1)*key combination because that's the only outwardly expressed thing in the encrypted file.

    Now, let's say that there was no recognizable pattern in the file. I could simply try all the numbers from 0 to 255 and see if adding that to half the set and subtracting from the other half would make a sensical file.

    The algorithm seems to be fairly weak to me. Here's pseudocode for cracking it:

    get file
    for each pair of characters
    flip them
    end for
    for i=0 to 255 do
    subtract i from all odd characters
    add i to all even characters
    test to see if the file makes sense
    end for

    Because you're using % as the final operand, you're directly reducing your key space. I'll post some suggestions later as to how to improve it and some other general techniques, I must leave for now.

    [edit] I'll have some free time tonight to code. If you could attach an encrypted file without giving me the keys, I'd like to write a short program to crack the file and then post the decrypted version. I think it'd prove useful and insightful. [/edit]

    [edit2] Fixed a technical error [/edit2]
    Is there a sum of an inifinite geometric series? Well, that all depends on what you consider a negligible amount.

  9. #9
    Senior Member
    Join Date
    Oct 2001
    Posts
    786
    AxessTerminated - Can you verify that this code is correct:

    Code:
     while(!in.eof())
    {
    in.get(ch);
    ch += key;
    ch += key2 * key;
    in.get(ch);      <-- Is that right?  or should it be ch2?
    ch2 -= key;
    ch2 -= key2 * key;
    out.put(ch2);
    out.put(ch);
    }
    And has this program successfully decrypted a file it has encrypted? I'm kind of confused because the disk writing routines does a "mod 255" ( %255 ) to get a valid character to write to the disk (ie, 1000 becomes 235, etc). I just need a yes/no, because I don't want to get to coding again to check a possible sceneario, and I don't want to code just to get valid numbers to see if it works or not. So a simple yes/no will suffice.



    Also, I don't think __int64 will work unless you have a 64bit processor and are compiling it for a 64bit version of Windows or Linux. I don't know if mingW (or whatever DevC++'s compiler is) can create a 64bit Windows Binary, since it is a Windows port of GCC/GPP for Linux and probably makes 64bit Linux code... You might want to begin using arrays of either long or int variables and you might find it could be easier to keep track of if you want to scale your program beyond even / odd lines. And BTW, I think the way this is done takes your 2^47 combinations and puts their output onto 16bits of space. If they can find a pattern strong enough, it might be possible (no idea if it has ever been done though) they can sort of "pick up" where rand() and its seeding go from there to decrypt the file without knowing the original key? Just one of the things that is twisting my mind enough that I need to get some more sleep or coffee or something.

    Another thing bothering me is that key1 appears to be biased to being non-random. Although it is sort of based on the key... It somehow adds the extra step of complexity that makes this take so much more time to consider, although what it does is obvious. I have a weak guess that what you did there can acturally lead to being able to prove if a certain key combination is down-right wrong and impossible, and thus save the time needed to brute force this. Of course, only after you calculate which combinations aren't possible can you avoid them, and it takes long enough to do that, that we would only consider it if you wanted to use this a lot in the future. But it probably does weaken security.


    And FlamingRain might be on to something. I should keep an eye on this.

  10. #10
    Senior Member
    Join Date
    Jan 2004
    Location
    Hawaii
    Posts
    351

    Lightbulb A fix, and other crap..

    Tim_Axe,
    You are correct, that line is suppose to be "in.get(ch2);"
    And, yes, this algorithm has encrypted, and decrypted many files without flaw. Where I ran into problems was with text files, due to the character translations.

    Flaming_Rain,
    I, too, am a math-lover, but I haven't actually made it to log() yet. (damn homework average, i failed algebra. so im going into algebra II this year) So could you explain that one to me?

    I will be including an attachment of a file, and its encrypted complement. Also, the source will be included. I can't attach them now, due to a few technical difficulties that are really pissing me off. Such as; only half my RAM is being recognized by windows...

    A_T
    Geek isn't just a four-letter word; it's a six-figure income.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •