Cracking this algorithm.
Page 1 of 2 12 LastLast
Results 1 to 10 of 13

Thread: Cracking this algorithm.

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

    Angry Cracking this algorithm.

    Alright, a friend of mine wrote a simple encryption scheme...much like the one i posted not too long ago. I've been attempting to crack it, and don't think I completely understand how to do so. I'll post his src, and my crack. As a side note, I've been challenged to crack it. I have one month, and I cannot brute force.

    Encryption Scheme:

    Code:
    #include <iostream.h>  //for cin and cout
    #include <string.h>  //for strcpy()
    #include <fstream.h>  //for ifstream and ofstream
    #include <stdlib.h>  //for system() and srand() and rand()
    #include <sys/stat.h>  //for stat() and stat structure
    
    int main(void)
    {
        char file[1024];  //to hold file path
        cout << "File to Encrypt: " << flush;
        cin.getline(file, 1023); //input file path from user
        struct stat result; //this will hold the the file's size
        stat(file, &result); //get the file's size from it's path, and place it in the result structure
        unsigned long flen = result.st_size;  //set our local variable to the size of the file
        cout << flen << " Bytes.  Enter 1 if correct: " << flush;
        unsigned long key, choice;
        cin >> choice;
        if (choice != 1)  //verify that data is correct before continueing
        {
            return 0;
        }
        cout << "Key: " << flush;
        cin >> key;  //input the encryption key
        cout << "Enter 1 if you are encrypting, 0 if decrypting: " << flush;
        cin >> choice;
        bool e_or_d;
        switch (choice)  //set encrypt or decrypt
        {
            case 0: e_or_d = false;
                    break;
            case 1: e_or_d = true;
                    break;
            default: return 0;
        }    
        system("cls");  //clear the screen
        cout << "Verify" << endl
             << "------" << endl
             << "File: " << file << endl
             << "Size: " << flen << endl
             << "Key : " << key << endl;
        if (e_or_d)
        {
            cout << "Encrypting" << endl;
        }
        else
        {
            cout << "Decrypting" << endl;
        }
        cout << endl
             << "Enter 1 if this is correct: " << flush;
        cin >> choice;
        if (choice == 0)  //verify that all data is correct again
        {
            return 0;
        }
        system("cls");
        cout << "Encrypting, standbye..." << flush;
        ifstream in(file, ios::binary);  //open our file
        strcpy(&file[strlen(file)], ".eng"); //this will turn something like C:\hello.txt into C:\hello.txt.eng
        ofstream out(file, ios::binary | ios::trunc);  //open our output file
        char buf;  //our buffer
        unsigned long x;  //counter variable
        srand(key); //randomize by the key
        for (x = 0; x < flen; x++) //loop until we've reached all bytes
        {
            in.get(buf);  //get 1 byte from file
            if (e_or_d)
                buf += (rand() % 713) - 331;  //encrypt it using this function.  To decrypt it's -=
            else
                buf -= (rand() % 713) - 331;  //decrypt it
            out.put(buf);  //output the new byte
        }
        out.flush();  //make sure everything has been written to the disk
        in.close();  //close file
        out.close();  //close file
        cout << "done" << endl << endl
             << "Saved as " << file << endl << endl
             << "Goodbye\n" << flush;  //closing message
        system("pause");  //pause
        return 0; //end program
    }
    He encrypted a file called hellokittyenc.txt. I am attempting to crack it, and output to hellokitty.txt. I assumed that all of the letters in his file (it is plaintext) would all have the same number added to it, and would be one of the 256 characters in the ASCII table. I don't understand why my crack doesn't work. The only things that come to mind are problems with character translations opening that TXT in binary mode...but he has successfully encrypted/decrypted it with the key. Any suggestions?

    NOTE: While running the program, I pause every 20 or so, and view the output to see if it's turned into plain english, if not I resume for another 20 or so. I have to stop every once in a while, because the cmd screen will not scroll all the way back up to view the first like 200 attempts.

    Code:
    #include <iostream.h>
    #include <fstream.h>
    
    
    
    char tmp;
    int x = 0;
    
    main()
    {
        for(x = 0; x <= 255; x++)
        {
            ofstream out("hellokitty.txt", ios::binary | ios::trunc);
            ifstream in("hellokittyenc.txt", ios::binary);
            
            while(!in.eof())
            {
                    in.get(tmp);
                    tmp -= x;
                    out.put(tmp);
            }
            
            out.flush();
            in.close();
            out.close();
            cout << "Code: " << x << endl;
            system("type hellokitty.txt");
            cout << endl;
            cout << "Attempted Decryption Complete\n";
            cout << endl;
        }
        
        system("pause");
            
    }
    Geek isn't just a four-letter word; it's a six-figure income.

  2. #2
    Senior Member
    Join Date
    Oct 2001
    Posts
    786
    The reason the single character thing that was mentioned in the last couple of crypto-related posts is because the number was never changed for every byte. The algorithms that used that did not change the number, leaving that possiblity open.

    The code here calls the random function again to encrypt. So that won't work.

    Code:
    in.get(buf);  //get 1 byte from file
            if (e_or_d)
                buf += (rand() % 713) - 331;  //encrypt it using this function.  To decrypt it's -=
    I bolded what I am stressing. rand() and where it is located.


    What happens is that for each byte, a new random number is calculated. But since the rand() function is 100% predictable, it can be used for reliable encryption and decryption. This is where we can begin attacking the code...


    We know the key is used to seed the random number generator. We also know for a fact that rand() produces a signed 16bit number, but only returns the positive range. This is essentially half of the 16bits, or 15bits. This raises the problem called collisions. Collisions are things where more than one key (the key the user types in for this program) can produce the same output as another key. Provided I am right with everything, we know we can "crack" the file within (2^16)/2 -- (really 2^15) guesses, or 32768 guesses.

    It is in a range where brute forcing is easy. You will need to brute-force to figure out the key, or one of its collisions. If an algorithm can't withstand some brute-force attacks after some analysis, it isn't very good. Basically, all we do is analyze it to see if we can make brute-forcing a painless task, and here it is. Due to limits of implementation, we can brute-force it in 2^15 tries. This is a sorry number of tries. Personally, I don't mind calculating 2^15 combinations, but when things get to like 2^32 combinations, I draw the line and won't bother working on it because it would begin to take way too long from there on.

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

    For your code, you need to implement what he did with the random number generator into your code. Basically, have a loop that seeds the random number generator numbers from 1 to 32768 or so, and then it does the decryption stuff. The decryption stuff would call rand() again and again, changing the seed value while doing so. But when it gets to the end, and it doesn't look right, it will seed rand() with a new number. It will change slowly because of what rand() does, so sifting through the output is easier because once it begins to look recongnizable, within a few tries of that it will become even clearer, etc. Anyways, give that a shot.

  3. #3
    Senior Member
    Join Date
    Jul 2003
    Posts
    813
    Tim_axe made a really good point there... just as a helper in future decrypting challenges, you should place all the output in a file [through the command prompt]. Sure you need to check it, especially if it's increasing in size too much. Make sure the cracking/brute-forcing program outputs the seeds as well so you know where you left off, and then go to the code and change it.

    I know it doesn't sound elegant. You could make the program take the starting seed in from the command prompt, or dump it/reload it from a file. But the important part is that you're trying to break something, and however you manage to get the job done is up to you
    /\\

  4. #4
    Senior Member
    Join Date
    Jan 2004
    Location
    Hawaii
    Posts
    351
    well the agreement was that i can't brute force it. what i assumed was brute-force on this algorithm was starting x at 0, and x++ until 32768. and each time x++, i srand(x), and attempt to decrypt it. is there any other way? frequency analysis wouldn't work because of te character translations in opening that TXT in binary mode.

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

  5. #5
    Senior Member
    Join Date
    Jan 2004
    Location
    Hawaii
    Posts
    351
    Well, he encrypted a text file..with a rude message to me. I know the first word is "Hello". So what I did is start with x=-32767 (the lowest INT goes) and subtract that from the first byte in the file. If it didn't yield an 'H', I incremented x by one, not exceeding the maximum of INT (32768). The 'H' is decrypted by the number -32571, and again on every increment of 256 following that.

    So on the next time around, I subtracted -32571 from the first byte, and ran the same test on the second byte with x, until I found the string 'Hello'. I don't know what comes after 'Hello', so I don't know where to go from here. I suppose I could brute force it by srand(x), but srand() takes an unsigned long int, which is 0 - 4,294,967,295...so that's alot of possibilities seeing as I'd have to seed rand() that many times and test the file. If I'm stumped, I'll do a brute force overnight to atleast get the code, then using that code, I could figure out some sort of other pattern, possibly. I don't want to encrypt my own file with a password, and brute force that, knowing the key...because I know his TXT doesn't have any type of problems (i.e. character translations).

    I can see why my original crack did not work either. I was subtracting x (a constant within that loop) from every byte. Which means if x=109, then 109 was subtracted from every byte. But he adds a random number to one byte of the file, then another random number to the next byte, and so on and so forth.

    Here is the crack that I've been using for the first 5 bytes. I changed the output file for the results everytime (i.e. results_1.txt to results_2.txt). Also, lower in the code, where 'i' is initialized within a for loop. If I'm trying to find 'Hel', then the for loop becomes:

    Code:
    while(!check.eof())
            {
                for(int i = 0; i < 3; i++)
                {
                    check.get(buf[i]);
                }
                    if(!strcmp(buf, "Hel"))
                    {
    Here's the code, in it's entirety. I commented out all the tmp += crap at the start, because those will only work for those first 5 bytes that I already know.

    Code:
    #include <iostream.h>
    #include <fstream.h>
    
    
    
    char tmp;
    char buf[6];
    int x = 0;
    ofstream result("results_5.txt", ios::trunc);
    main()
    {
        //for(x = -331; x <= 682; x++)
        //for(x = -32768; x <= 32767; x++)
        for(x = 0; x < 32767; x++)
        {
            ofstream out("hellokitty.txt", ios::binary | ios::trunc);
            ifstream in("hellokittyenc.txt", ios::binary);
            while(!in.eof())
            {
                /*
                in.get(tmp);
                tmp -= -32571;
                out.put(tmp);
    
                in.get(tmp);
                tmp -= -32672;
                out.put(tmp);
                
                in.get(tmp);
                tmp -= 246;
                out.put(tmp);
                
                in.get(tmp);
                tmp -= 212;
                out.put(tmp);
                */
                
                in.get(tmp);
                tmp -= x;
                out.put(tmp);
                
            }
            
            out.flush();
            in.close();
            out.close();
            result << "Code: " << x << endl;
            cout << "Code: " << x << endl;
            //FINDS 'H' ON CODE: -32571 AND ALL INCREMENTS OF 256 FOLLOWING
            //FINDS 'He' ON CODE: -32672 AND ALL INCREMENTS OF 256 FOLLOWING
            //FINDS 'Hel' ON CODE: 246
            //FINDS 'Hell' ON CODE: 212
            //FINDS 'Hello' ON CODE: 122
            ifstream check("hellokitty.txt", ios::binary);
            while(!check.eof())
            {
                for(int i = 0; i < 5; i++)
                {
                    check.get(buf[i]);
                }
                    if(!strcmp(buf, "Hello"))
                    {
                        result << "Possible Decryption!\n";
                        cout << "Possible Decryption!\n";
                        check.close();
                        system("type hellokitty.txt");
                        result << "[see hellokitty.txt]";
                        result << "\nIf this is a match, close bet_crack now.\n";
                        cout << "\nIf this is a match, close bet_crack now.\n";
                        system("pause");
                        break;
                    }
    
                    else
                    {
                        break;
                    }
                }
    
            result << "Attempted Decryption Complete\n\n";
            cout << "Attempted Decryption Complete\n\n";
    
        }
        result.close();
        system("pause");
            
    }
    Still looking for suggestions.

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

  6. #6
    Senior Member
    Join Date
    Oct 2001
    Posts
    786
    What you should try to do is to find all of the seeds (srand()) that produce a random-number (rand()) that could be used to make the right values (-32571, etc) to successfully decypt the first character. I *think* you only need to worry about numbers between 0 and 32768 when seeding. Then, if the first seed works, try for the second one (call rand() again) and see if that gets what you know is the 2nd character. If it doesn't, re-seed incrementally (0 to 32768) and try again until it happens.

    So in this isolated sceneario, your goal is to find the right key. After you have the key, you can easily get the message. Spliting those two things up might be important.

    Basically (I think you've already described the process a bit in your code):
    Load encrypted file
    Seed the random-number generator from 0 to 32768 (loop)
    ->Get a random number, use his formula, and check if the output is "H"
    -> ->If the output is "H", get another random-number, and check if the output is "e"
    -> -> ->You probably have the right initial seed if you get "He" - you've cracked the key for that file
    -> ->If the output is not "H", then increment the seed since this one isn't working...
    -> (End Loop)
    Display the initial seed
    Modify his program to use that initial seed to decrypt the whole file -- since the first one just figures out the key for you based on known-plaintext type attacks.


    I don't have time to code anything, but I think the pseudo-code should get you somewhere. What I described is limited to only encrypted files that you know the first couple of (decrypted) characters for with this paticular algorithm/formula. If your friend won't tell you what the first character is for some file, you'll have to resort to more manual ways of checking/brute-forcing...

    Good luck.

  7. #7
    Senior Member
    Join Date
    Jan 2004
    Location
    Hawaii
    Posts
    351
    Thanks Tim_Axe. The problem is, srand() returns an unsigned long int. So there are over 4 billion seeds to test out. Then he +='s the byte with rand(), modulous, and subtraction, which actually drops the maximum 'hash' to -331 -> 682. 'Hash' meaning the number that the byte is actually encrypted with. So I'd have to find which srand() that produces these keys. But I'm looking for a more universal way. As if I've intercepted a file and have no clue what the first characters are. If you could explain that manual way..while keeping it as a non-bruteforce attack, that would be of great help. If you don't have time to code, pseudo-code is also well appreciated. Right now, I'm working on a brute force...having a few troubles. But I figure if i can get one key, and the resulting encryption, it would be of some help.
    Geek isn't just a four-letter word; it's a six-figure income.

  8. #8
    Senior Member
    Join Date
    Oct 2001
    Posts
    786
    Although srand() will take an unsigned long int, it has issues with collisions when you call rand(). Check the following code out:

    Code:
    #include <stdlib.h>
    
    int main ( void )
    {
        long key1 = 0, key2 = 0;
        
        srand(key1);
        
        while (printf("When seed is %i, output is %i\n", key1, rand()))
        {
            srand(key1++);
        }
        
        getch();
        return 0;
    }
    When you run it, you will eventually find that there are collisions. Here is an example after running the program for approximately 4 seconds on my computer, piping the input into a file:

    D:\My Projects\AntiOnline\261497>main > output.txt
    ^C
    D:\My Projects\AntiOnline\261497>egrep ", output is 38$" output.txt
    When seed is 0, output is 38
    When seed is 1, output is 38
    When seed is 30104, output is 38
    When seed is 60207, output is 38
    When seed is 80276, output is 38
    When seed is 110379, output is 38
    When seed is 140482, output is 38
    When seed is 170585, output is 38
    When seed is 220757, output is 38
    When seed is 250860, output is 38
    When seed is 280963, output is 38
    When seed is 311066, output is 38
    When seed is 331135, output is 38
    When seed is 361238, output is 38
    When seed is 391341, output is 38

    D:\My Projects\AntiOnline\261497>egrep ", output is 3$" output.txt
    When seed is 20059, output is 3
    When seed is 50162, output is 3
    When seed is 80265, output is 3
    When seed is 100334, output is 3
    When seed is 130437, output is 3
    When seed is 160540, output is 3
    When seed is 190643, output is 3
    When seed is 240815, output is 3
    When seed is 270918, output is 3
    When seed is 301021, output is 3
    When seed is 331124, output is 3
    When seed is 351193, output is 3
    When seed is 381296, output is 3

    D:\My Projects\AntiOnline\261497>
    This means you don't have to do 4 billion combinations to find the collisions you're looking for. You could do about 32768 tries to find a collision, although as a safety-overlap you could go to like 40000 tries or more, but it isn't necessary.


    One brick at a time



    Edit: Although to be honest, I don't know if srand() has any effect on later seeds. IE, even if seeds 30104 and 391341 produced an initial random number of 38, would the next random number be different than something that was seeded originally with 38, or different from each other? I think it will be the same; however I have not acturally tested this.

    Edit2: The code is code from another post on AO. I haven't cleaned it up, so some variables remain unused.

  9. #9
    Senior Member
    Join Date
    Jan 2002
    Posts
    1,207
    The problem with this "algorithm" is that it is ENTIRELY dependent on your C library's implementation of rand() and srand().

    This means that different C libraries, will almost certainly result in files which cannot be decrypted at all. rand() should not be relied on performing the same on every C library.

    HOWEVER, yes most of the above points do stand. There is one thing I'd like to mention though:

    Tim_axe said that you could find collisions in srand() by calling it, and comparing the first value you get from rand(). This is not, however, true, because rand() produces a sequence of numbers, not just one. You can't just compare the first value, you need to check the entire (infinite) sequence. However, because we know that the period of rand() must be finite, it's sufficient to check the entire period. In practice, I'd suggest it's acceptable to just check the first 8 or so values - which are extremely unlikely to be the same if the sequence is different.

    So there might be a lot less collisions than Tim_axe suggests.

    Additionally the number of collisions could be as low as 0 (in the 32-bit keyspace).

    On 64-bit machines this algorithm is likely to be extremely different. rand() will still only return 1-32k, but the random state may be 64-bit instead, so the period larger. The keysize could be bigger.

    Slarty

  10. #10
    Senior Member
    Join Date
    Jan 2004
    Location
    Hawaii
    Posts
    351
    I'm running a brute-force now. Well, two to be exact. I don't know how to thread, so I just have two instances of the program running. One started with x = 0, srand(x), x++. The other started at x = 4294967295, srand(x), x--. At least this way, it runs twice as fast. Time to set priority to high and let you guys know the outcome. Now, this is the brute-force, which will now satisfy the deal with my friend. I'm still clueless on how to go about cracking this without trying every combonation. Thanks again.

    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
  •