For Queatrix

This is a discussion on For Queatrix within the A Brief History of Cprogramming.com forums, part of the Community Boards category; How I broke Queatrix' encryption: I started by writing up a small program to do frequency analysis on varying chunk ...

  1. #1
    C++ Developer XSquared's Avatar
    Join Date
    Jun 2002
    Location
    Ontario, Canada
    Posts
    2,718

    For Queatrix

    How I broke Queatrix' encryption:

    1. I started by writing up a small program to do frequency analysis on varying chunk sizes. Since the size of the file (951 bytes) is only divisible by 3 and 317, I checked for chunk sizes of 1 and 3 bytes. There were a total of 57 1-byte patterns, and 260 3-byte ones, so I assumed that it was a relatively simple substitution/modification cypher which only operated on single bytes with a one-byte key.
    2. Looking at the output from my frequency calculator, I noticed that all of the results had one of the following hex characters in their four most least significant bits: 2, 3, 6, a, b, e and f. Looking at the binary representations of these numbers revealed that in every case, the 2nd least significant bit was set. I presumed this to mean that the data encoded was 7-bit ASCII, with a 1 inserted there for no apparent reason.
    3. Then I looked at the most frequently occuring character: 0xFB with 129 occurences. Since I was working under the assumption that I was dealing with an english-language plaintext, it was a safe bet that this was the space character.
    4. Examining the binary representation of 0xFB, I noticed that it is an inverted mirror image of the space character (0x20). Thus, my first guess at your encryption method was that you were simply NOTing the bytes and reversing the order of bits.
    5. I then turned my attention to the next most frequent characters, 0x9A, 0xBA, 0x4A and 0xAA. Still under the assumption that the plaintext was in English, I assumed that three of those four represented the three most common letters in English: 'e', 't', and 'a'.
    6. I applied my first guess at your encryption algorithm to these characters, and realized that they didn't match up, which showed me that I was incorrect in my guess.
    7. Looking at the binary representations of all of the above (plaintext and NOTted values), I realized that 'a' and 't' differ by one bit, as do 'e' and 'a'. Looking at the encrypted values, I realized that 0x9A and 0xBA differ by one bit, as do 0xBA and 0xAA. I thus assumed that 0xBA was the encrypted version of 'a'. With that assumption, I also assumed that the more frequent of the two remaining (0x9A) represented 'e', while 0xAA represented 't'.
    8. Upon realizing that the NOTed versions of the encrypted characters had the same number of set/unset bits as their plaintext equivalents, I realized that what was most likely happening was that the bits were being swapped around.
    9. To determine where the swapping occured, I wrote all four plaintexts in binary form one above the other, and then did the same thing with the NOTed encrypted values, to get the following:

      Code:
      00000100 00100000
      01100101 01100101
      01000101 01100001
      01010101 01101001
    10. I then looked to see which columns were unique, and where they appeared on each side. I found that column 4 in the encrypted table moved to column 4 in plaintext, and that columns 3 and 6 switched places. Columns 1, 2, 7 and 8 seemed to stay in place.
    11. I then wrote a quick program to test my theory by having it swap columns 3&6 and 4&5 in the file, and realized when I looked at the output that only some characters were decrypted (such as 'a', 't', etc.).
    12. After modifying my application to swap colums 1&7 and 2&8, I ran it again and got the plain-text. Voila.
    Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah

    You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie

  2. #2

    Join Date
    May 2005
    Posts
    1,041
    g'job!
    I'm not immature, I'm refined in the opposite direction.

  3. #3
    Registered User Queatrix's Avatar
    Join Date
    Apr 2005
    Posts
    1,342
    Pretty nice.
    Think you could do a harder one?

  4. #4
    C++ Developer XSquared's Avatar
    Join Date
    Jun 2002
    Location
    Ontario, Canada
    Posts
    2,718
    I honestly doubt I could do anything harder than this one by just looking at a piece of ciphertext. Given a number of plaintext/ciphertext combos, I may be able to crack something harder.
    Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah

    You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie

  5. #5
    Slave MadCow257's Avatar
    Join Date
    Jan 2005
    Posts
    735
    Where is Queatrixes encryption explained

  6. #6
    C++ Developer XSquared's Avatar
    Join Date
    Jun 2002
    Location
    Ontario, Canada
    Posts
    2,718
    The initial thread was basically him saying "break this" with an attachment on the post, no explanation/plaintext given. It as lost during the board's downtime/rollback, unfortunately. I've attached the file he provided.
    Attached Files Attached Files
    Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah

    You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie

  7. #7
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    Quote Originally Posted by XSquared View Post
    I honestly doubt I could do anything harder than this one by just looking at a piece of ciphertext. Given a number of plaintext/ciphertext combos, I may be able to crack something harder.
    You beat me by a mile on the original.

    But regarding something a little different, this is an old curiosity of mine:
    Attached Files Attached Files
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  8. #8
    C++ Developer XSquared's Avatar
    Join Date
    Jun 2002
    Location
    Ontario, Canada
    Posts
    2,718
    That's much trickier, Dave. Bastage.
    Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah

    You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie

  9. #9
    C++ Developer XSquared's Avatar
    Join Date
    Jun 2002
    Location
    Ontario, Canada
    Posts
    2,718
    I'm stumped at the moment, Dave. Any chance you could provide another couple cipher+plain combos (data of your choice)?
    Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah

    You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie

  10. #10
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    Quote Originally Posted by XSquared View Post
    I'm stumped at the moment, Dave. Any chance you could provide another couple cipher+plain combos (data of your choice)?
    Here's another pair for the moment.

    (And it's not RSA, AES, DES, etc. or such like that.)
    Attached Files Attached Files
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  11. #11
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    And another pair, I don't know if this is too much of a hint or not.
    Quote Originally Posted by plain.txt
    This is more secure that the first, but not by much. This basic algorithm, with a few variations, is the most common "home grown" encryption algorithm. [...] It takes only a minute or two [...]. The messages could be decoded and the key discovered very easily without even invoking elementary cryptanalysis. [...]
    Attached Files Attached Files
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  12. #12
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    The source (my version at least, encrypted of course):
    Attached Files Attached Files
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  13. #13
    Lean Mean Coding Machine KONI's Avatar
    Join Date
    Mar 2007
    Location
    Luxembourg, Europe
    Posts
    444
    I'm just guessing (didn't even look at the plain/cipher text) but maybe you used a "mode of operation" on the plaintext, an iterative XOR operation with an initial vector which represents your key ? Depending on what mode you've chosen, I could start looking for first-block conflicts or similar known problems but I'm not a huge fan of cryptanalysis.

  14. #14
    C++ Developer XSquared's Avatar
    Join Date
    Jun 2002
    Location
    Ontario, Canada
    Posts
    2,718
    Aah. Xoring with a seeded random number generator. Not portable, unfortunately. I doubt I would have ever broken it (if you hadn't posted the encrypted source code), due to the fact that the RNG on my machine gives different output than the one on the machine that encrypted these text files.
    Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah

    You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie

  15. #15
    C++ Developer XSquared's Avatar
    Join Date
    Jun 2002
    Location
    Ontario, Canada
    Posts
    2,718
    Also, as for how I cracked it, I had a program which XORed two arbitrary files, and when I ran it on multiple sets of plain/ciphers, I noticed that the result was the same. I had no clue how he was generating the key, so I just XORed the data file with the encrypted source to get the plain-text source.
    Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah

    You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21