Page 1 of 3 123 LastLast
Results 1 to 20 of 50

Thread: Cryptography : is it me ???

  1. #1
    Join Date
    Jan 2006
    Location
    travelling
    Posts
    1,116
    Thanks
    8
    Thanked 127 Times in 121 Posts
    Qt products
    Qt4
    Platforms
    Unix/X11 Windows

    Default Cryptography : is it me ???

    Hi,

    I am currently writing some kind of paper on algorithms for school and I thought about cryptography to illustrate my work with examples. However when googling around I only found very complicated and time-consuming things without much explanations on the principle : WEP, WPA, Blowfish...

    So I took my pencil, unleashed the power of my mind
    and I came to the following code which as you can see is a rather lightweight, though very powerful, XOR crypto :
    Qt Code:
    1. // this function is called encrypt but is actually a "state-switcher"...
    2. void encrypt(QByteArray& data, const QByteArray& pass)
    3. {
    4. for ( int i = 0; i < data.count(); i++ )
    5. data[i] ^= pass.at(i % pass.count());
    6. }
    To copy to clipboard, switch view to plain text mode 

    My question is : Why isn't such a method used everywhere ??? It has many advantages and, provided a shared key is affordable, no real drawbacks AFAIK...

    Just to convince you here are some figures :
    • A WEP passphrase is something like 10 ASCII chars long, which, you shall admit, corresponds to 10*8 = 80 bits
    • Using a passphrase of this size (which is rather reasonable) in my homemade encryption function gives 2^80 = more than 1.2*10^24 possible combinations
    • Assuming one attempts a "brute-force" cracking of a 100 characters long text message encoded with the aforementioned key he will have to try decoding the message with each of these combinations and then check if it is likely to be a message...
    • Assuming 100 T-states for each pass of the encoding/decoding loop we have 100*100 = 10.000 T-states for each encoding/decoding.
    • With luck the brute-force attack can find the correct key after 2^40 attempts (sounds a lot ? try it and you'll see that it would be quite a luck indeed...). That would take him : 10.000 * 2^40 = 1.1*10^16 T-states
    • You're not used to measure time with T-states are you? So let's convert that to common units. Assuming the cracker uses a 3GHz processor fully dedicated to the task (which never happens but we'll discard hardware questions here...), the attack will last : 1.1*10^16 / 3*10^9 = 3.665.039 seconds = 1018 hours = 42 days and an half : about a month and an half!!! For a simple text message encoded using a WEP-like key!!!
    However I'm not a specialist of cryptography and may have missed something very important. Thus I'd appreciate if someone could answer my question : Why isn't it used everywhere???
    Current Qt projects : QCodeEdit, RotiDeCode

  2. #2
    Join Date
    Jan 2006
    Location
    Alingsås, Sweden
    Posts
    437
    Thanks
    3
    Thanked 39 Times in 39 Posts
    Qt products
    Qt3 Qt4
    Platforms
    Unix/X11 Windows

    Default Re: Cryptography : is it me ???

    One reason not to use this method is that the same key is used for both decryption and encryption. Some modern encryption methods works with one public key used for encryption and a different, private, key for decryption. This means that the encryption key can be spread freely and the the decryption can be protected.

  3. #3
    Join Date
    Jan 2006
    Location
    travelling
    Posts
    1,116
    Thanks
    8
    Thanked 127 Times in 121 Posts
    Qt products
    Qt4
    Platforms
    Unix/X11 Windows

    Default Re: Cryptography : is it me ???

    I know that but as I stated this method is intended to be used only when the use of two different keys (a public and a private one) is not necessary. Wifi networks are encrypted without RSA-like cryptography for instance and this whatever the method used (WEP, WPA or anything else...) : there is one key know by the accesspoints and all the computers connecting to it...
    Current Qt projects : QCodeEdit, RotiDeCode

  4. #4
    Join Date
    Jan 2006
    Location
    Warsaw, Poland
    Posts
    33,359
    Thanks
    3
    Thanked 5,015 Times in 4,792 Posts
    Qt products
    Qt3 Qt4 Qt5 Qt/Embedded
    Platforms
    Unix/X11 Windows Android Maemo/MeeGo
    Wiki edits
    10

    Default Re: Cryptography : is it me ???

    Quote Originally Posted by fullmetalcoder View Post
    My question is : Why isn't such a method used everywhere ???
    Because it's easy to break

    In case the password is shorter than the input data, you're reusing the same password (this is called Electronic Code Book (ECB) mode), which is the same as if you encrypted two different messages with the same key - it's easy to break. Russian ciphers were compromised because of reusing the same key for multiple messages.

    It has many advantages and, provided a shared key is affordable, no real drawbacks AFAIK...
    To be honest it's pretty easy to break Furthermore it only encrypts the message but you can still change the contents, etc.

    Furthermore, try encrypting a message containing only zeros with your method and see what you get as output

    A WEP passphrase is something like 10 ASCII chars long, which, you shall admit, corresponds to 10*8 = 80 bits
    DES has 56 bit keys and it's considered quite safe (not counting the brute force attack, of course). But it's because the way the key is used.

    BTW. WEP is not safe because of its keylength. And the RC4 cipher used for Wi-Fi along WEP is not that good either. Usage of WPA with AES is advised.

    Using a passphrase of this size (which is rather reasonable) in my homemade encryption function gives 2^80 = more than 1.2*10^24 possible combinations
    This is nothing. You can make a brute force attack on it using parallel computing (http://distributed.net) - you'd have it broken within days.

    Assuming one attempts a "brute-force" cracking of a 100 characters long text message encoded with the aforementioned key he will have to try decoding the message with each of these combinations and then check if it is likely to be a message...
    Not quite. You can limit the number of possibilities by making comparisons knowing the key length.

    With luck the brute-force attack can find the correct key after 2^40 attempts (sounds a lot ? try it and you'll see that it would be quite a luck indeed...). That would take him : 10.000 * 2^40 = 1.1*10^16 T-states
    Even for 2^80 combinations (provided you encrypt messages shorter than the key length) with computers that can do about 2^31 operations per second (for single core 2GHz processors) you only need ~2^50 second with a single processor or 2^40 seconds for 1000 computers, etc. It's not that much.

    1.1*10^16 / 3*10^9 = 3.665.039 seconds = 1018 hours = 42 days and an half : about a month and an half!!!
    You can break a static key WEP protected network after listening for the traffic for ~4 hours and some time to process the sniffed data.

    You can strenghten the cipher by using some feedback mode with your method for messages longer than the key (http://en.wikipedia.org/wiki/Block_c..._of_operation).

    But your cipher is still very weak for shorter messages using a known plaintext attack (you know the plain text, you know the cipher text, you try to find the key).

    Quote Originally Posted by e8johan
    One reason not to use this method is that the same key is used for both decryption and encryption. Some modern encryption methods works with one public key used for encryption and a different, private, key for decryption. This means that the encryption key can be spread freely and the the decryption can be protected.
    Symmetric ciphers are used everywhere, including SSL. Assymetric systems have a wider range of use than symmetric ones and they are safer, because they require more time consuming operations than symmetric ones (the keys are much longer) and additionally you can't implement them in hardware efficiently. For example you can assure that the message is not changed, you can be sure that the message was not forged by someone else, etc.

  5. #5
    Join Date
    Jan 2006
    Location
    Warsaw, Poland
    Posts
    5,372
    Thanks
    28
    Thanked 976 Times in 912 Posts
    Qt products
    Qt3 Qt4
    Platforms
    Unix/X11 Windows

    Default Re: Cryptography : is it me ???

    Quote Originally Posted by wysota View Post
    Because it's easy to break
    Precisely, but how easy? Let's see:

    Suppose we have a XOR-encrypted file out.txt. It's a paragraph from a book, not that it's my favorite one, but it's quite long and available at Guthenberg project's site, so it's useful when you want to play with some text-handling algorithms.

    First let's compute the number of coincidences for every possible key length. How to do that? We just have to compare all bytes that were encrypted using the same character and see how many of them are equal.

    I wrote a small script that automates this:
    $ ./coin.py < out.txt > coin.txt
    If we plot the contents of coin.txt file we will get something like this:
    coin.png
    Clearly the number of coincidences is significantly larger if we assume that the key length is 8, 16, 24, 32 and so on, so most likely 8-byte key was used.

    Now if we divide the cryptogram into 8 groups, so that each group contains bytes that were encrypted using the same character, and find the most frequent byte in each group we will get this:
    $ ./hist.py 8 < out.txt
    0: best=77 count=27
    1: best=79 count=22
    2: best=66 count=25
    3: best=89 count=22
    4: best=68 count=29
    5: best=12 count=22
    6: best=67 count=23
    7: best=75 count=23
    Possible password: ********
    Now a small riddle: what is the most frequent character in texts?

    Finding the password and decrypting the text is left as an exercise for the reader.

    Now if you were using XOR to encrypt packets, the job would be event simplier, because you can easily predict values of certain fields, like version or protocol number.
    Attached Files Attached Files

  6. #6
    Join Date
    Jan 2006
    Location
    Warsaw, Poland
    Posts
    33,359
    Thanks
    3
    Thanked 5,015 Times in 4,792 Posts
    Qt products
    Qt3 Qt4 Qt5 Qt/Embedded
    Platforms
    Unix/X11 Windows Android Maemo/MeeGo
    Wiki edits
    10

    Default Re: Cryptography : is it me ???

    Quote Originally Posted by jacek View Post
    Precisely, but how easy?
    With a known plaintext (like in case of network protocols) the complexity of finding the password is O(1). Just xor the ciphertext with the plaintext. No need to determine key length or anything.

    It's a paragraph from a book, not that it's my favorite one, but it's quite long and available at Guthenberg project's site, so it's useful when you want to play with some text-handling algorithms.
    A wild guess - Moby Dick?

    Now a small riddle: what is the most frequent character in texts?
    \x20?


    Now if you were using XOR to encrypt packets, the job would be event simplier, because you can easily predict values of certain fields, like version or protocol number.
    You can go even further here. Some fields have exactly specified values (mostly zeros) and there is also padding involved (most often a one and zeros again). Network addresses can also be used (broadcast, source and destination), but zeros are certainly the best
    Some Operating-Systems-With-Faulty-TCP/IP-Implementations (C) make the life harder here as they tend to ignore some rules and standards (for instance not zeroing fields that should be set to zero as they assume nobody will read them anyway, so why bother? Let's leave the trash that was in that block of memory (maybe some password, credit card number or email address?) in the packet).

  7. #7
    Join Date
    Mar 2006
    Location
    Mountain View, California
    Posts
    489
    Thanks
    3
    Thanked 74 Times in 54 Posts
    Qt products
    Qt3 Qt4 Qt/Embedded
    Platforms
    MacOS X Unix/X11 Windows

    Default Re: Cryptography : is it me ???

    If you want a good example of an encryption algorithm, take a look at IDEA. It's not at all trivial, but on the other hand, it's fairly easy to understand (the "how" if not the "why"). While it is probably under patent, you're using it in a classroom, so it shouldn't be a problem. There was an article on it in an early 1990's DDJ that was very good. MD5 is also another fairly easy cryptography algorithm.

  8. #8
    Join Date
    Jan 2006
    Location
    travelling
    Posts
    1,116
    Thanks
    8
    Thanked 127 Times in 121 Posts
    Qt products
    Qt4
    Platforms
    Unix/X11 Windows

    Default Re: Cryptography : is it me ???

    Quote Originally Posted by wysota View Post
    Because it's easy to break

    In case the password is shorter than the input data, you're reusing the same password (this is called Electronic Code Book (ECB) mode), which is the same as if you encrypted two different messages with the same key - it's easy to break. Russian ciphers were compromised because of reusing the same key for multiple messages.

    To be honest it's pretty easy to break Furthermore it only encrypts the message but you can still change the contents, etc.
    That easy??? My understanding was that the only way to break the code was a brute-force attack which would be very long... Jacek and you keep talking about "known plain-text attack" but I don't really see what you mean here... I view cryptography as a way to hide data using a key and not to hide a key in know data...

    Quote Originally Posted by wysota View Post
    Furthermore, try encrypting a message containing only zeros with your method and see what you get as output
    I'm sorry but I don't see any point in :
    • sending such a message
    • encrypting it if so
    Besides what tells you, when you want to decrypt the message in question that is was only zeros ??? it could be repeated characters but nothing helps you in guessing what they were before encryption...

    Quote Originally Posted by wysota View Post
    Not quite. You can limit the number of possibilities by making comparisons knowing the key length.

    But your cipher is still very weak for shorter messages using a known plaintext attack (you know the plain text, you know the cipher text, you try to find the key).
    My point here is that, assuming I send a message (plain text or not) through network, encrypted with my XOR method, if one intercepts it all he will know will be the encrypted message and he will try to find the original data without knowing the key (and not even its length). In this case the decyphering will be quite complicated won't it? Especially because it needs, at each step an accurate check to determine wether the key used led to clear-looking data which is likely to be the original data. This can get impossible if the encryption uses a second transformation (based on the key and possibly on another variable) before or after the XOR... Then, and only then, the key is known and later messages will be decrypted instantly but before that...

    Just to check wether you're right about the weakness of it, here is a small file (and redundant to make your task easier ) that I encrypted with a buffered, plain-Qt, version of the algorithm above... Encrypting took 79ms according to QTime (including statistics display and file I/O) which means an encrypting rate of about 15Mb/s... Your mission, if you accept it, is to decrypt this file before next Sunday and to tell me which key I used... If you managed to do that, you'd get... my eternal respect!

    Quote Originally Posted by wysota View Post
    Symmetric ciphers are used everywhere, including SSL. Assymetric systems have a wider range of use than symmetric ones and they are safer, because they require more time consuming operations than symmetric ones (the keys are much longer) and additionally you can't implement them in hardware efficiently. For example you can assure that the message is not changed, you can be sure that the message was not forged by someone else, etc.
    Well, asymmetric cyphers are quite powerful ATM but it might not remain true forever... Quantum mechanics is being studied so as to craft a quantic computer that would be able to do integer factorization *VERY FAST* directly from hardware and as RSA and other asymmetric cyphers depend on factorization of (big) prime numbers they are doomed to death (even if it won't happen tomorrow).
    Current Qt projects : QCodeEdit, RotiDeCode

  9. #9
    Join Date
    Jan 2006
    Location
    Warsaw, Poland
    Posts
    33,359
    Thanks
    3
    Thanked 5,015 Times in 4,792 Posts
    Qt products
    Qt3 Qt4 Qt5 Qt/Embedded
    Platforms
    Unix/X11 Windows Android Maemo/MeeGo
    Wiki edits
    10

    Default Re: Cryptography : is it me ???

    Quote Originally Posted by fullmetalcoder View Post
    That easy???
    Yep...

    My understanding was that the only way to break the code was a brute-force attack which would be very long...
    Nope.

    Jacek and you keep talking about "known plain-text attack" but I don't really see what you mean here... I view cryptography as a way to hide data using a key and not to hide a key in know data...
    Yes, but sometimes you just know what is being encrypted. For example if you know the message is probably about a "nuclear weapon", you can try matching the ciphertext to the plaintext and based on that get the key by xoring the ciphertext with the plaintext. Chances are the key is a phrase, which you can then guess by having a part of it.

    If you intercept a transmission between a man and a woman having an affair and the transmission takes place on the Valentine's Day, you can try to match the word "love", "miss", the names or even the phrase "I love you", "I miss you", etc.


    I'm sorry but I don't see any point in :
    • sending such a message
    • encrypting it if so
    This is where you're wrong. Files often contain blocks of zeros, so do network packets. And the "zero" case is just an example - you can do it with any known plaintext, the result will just not be that impressive (by xoring the key with zeroes you reveal the key yourself).

    If you transmit images or other kinds of files, you can look for file format headers or other known signatures. This is the exact same way antivirus software uses to detect polymorphic viri.

    Besides what tells you, when you want to decrypt the message in question that is was only zeros ???
    If I see a text which makes sense, I can guess it is a result of xoring a key with zeroes. Besides, I can:
    a) forge and plant a message that would get encrypted by you and then intercept the ciphertext and decrypt it by xoring it with the plain text.
    b) try my luck and assume there is a block of zeroes somewhere as padding, header or whatever.

    it could be repeated characters but nothing helps you in guessing what they were before encryption...
    You can always do statistics attack just like Jacek described - knowing the key length you know that each nth byte will be encrypted with a monoalphabet cipher.

    My point here is that, assuming I send a message (plain text or not) through network, encrypted with my XOR method, if one intercepts it all he will know will be the encrypted message and he will try to find the original data without knowing the key (and not even its length). In this case the decyphering will be quite complicated won't it?
    No. One can safely assume the key length (in bits) is divisable by eight. Then you have three ways - statistics, guessing the plaintext (for example network addresses, reserved fields, padding, etc.) knowing the transmission protocol or trial and error. Each of these will vastly decrease the number of tries needed to break the code.

    Especially because it needs, at each step an accurate check to determine wether the key used led to clear-looking data which is likely to be the original data. This can get impossible if the encryption uses a second transformation (based on the key and possibly on another variable) before or after the XOR...
    You proposed an algorithm that doesn't do anything like that. We're pointing weaknesses of the method you suggested, not any method that uses xor as one of its blocks. There are successfull ciphers that use xor to scramble data, but xor can't be the main safeguard used.

    Then, and only then, the key is known and later messages will be decrypted instantly but before that...
    As long as there exists a way to convert the cipher to a set of monoalphabetic ciphers, any text may be deciphered provided it is long enough.

    Just to check wether you're right about the weakness of it, here is a small file (and redundant to make your task easier ) that I encrypted with a buffered, plain-Qt, version of the algorithm above... Encrypting took 79ms according to QTime (including statistics display and file I/O) which means an encrypting rate of about 15Mb/s... Your mission, if you accept it, is to decrypt this file before next Sunday and to tell me which key I used... If you managed to do that, you'd get... my eternal respect!
    As we already said, you need an insight of what the message contains to decipher it. Most often, if you try to break a cipher, you know what you are looking for - at least you know the language used to write the message.

    Well, asymmetric cyphers are quite powerful ATM but it might not remain true forever...
    Assymetric ciphers are very simple. Their strength is based on difficulty to perform some mathematic operations, like factorising large numbers or finding a discrete logarithm of large numbers. There is nothing "powerful" about it.

    as RSA and other asymmetric cyphers depend on factorization of (big) prime numbers
    You can't factorise a prime number A prime number, by definition can't be factorised because it contains only two factors - 1 and itself.

    they are doomed to death (even if it won't happen tomorrow).
    Yes, but when computers become fast enough (or someone finds a fast algorithm) to calculate factors of large numbers in short time, messages encrypted will long have become outdated. You see, you rarely want to protect some data forever - you only need to protect it for a limited period of time - be it 20 minutes or 200 years. You don't have to use strong ciphers to protect your SSH sessions, because the session key is changed every 20 minutes or so, so if it takes someone 21 minutes to break the cipher, it will already be too late, as the connection will be using a different key then. And remember that the main goal of SSH connections is not to hide the content of the transmission, but to prevent one from hijacking the session by performing a man in the middle attack. SSH was designed as a method of securing terminal access, not to plan terroristic attacks.

  10. #10
    Join Date
    Jan 2006
    Location
    travelling
    Posts
    1,116
    Thanks
    8
    Thanked 127 Times in 121 Posts
    Qt products
    Qt4
    Platforms
    Unix/X11 Windows

    Default Re: Cryptography : is it me ???

    Quote Originally Posted by wysota View Post
    As we already said, you need an insight of what the message contains to decipher it. Most often, if you try to break a cipher, you know what you are looking for - at least you know the language used to write the message.
    Well, that's not always the case but I'll help you out : the language used in the sample encrypted file is C++ (with english comments) and many redundancy. Is that enough as an inside???

    Quote Originally Posted by wysota View Post
    Assymetric ciphers are very simple. Their strength is based on difficulty to perform some mathematic operations, like factorising large numbers or finding a discrete logarithm of large numbers. There is nothing "powerful" about it.
    There is something very powerful in them because they force the potential hacker to do many complicated computations or to pass away sobbing...

    Quote Originally Posted by wysota View Post
    You can't factorise a prime number A prime number, by definition can't be factorised because it contains only two factors - 1 and itself.
    Well, that's not what I meant... English is not my native language and hurry often causes nonsense... AFAIK RSA uses (big) prime numbers to encrypt data and a brute force attack would need factorizing encrypted data (into a product of prime numbers because, as everyone know, each integer can be described as a unique product of prime numbers...).
    Current Qt projects : QCodeEdit, RotiDeCode

  11. #11
    Join Date
    Jan 2006
    Location
    Warsaw, Poland
    Posts
    5,372
    Thanks
    28
    Thanked 976 Times in 912 Posts
    Qt products
    Qt3 Qt4
    Platforms
    Unix/X11 Windows

    Default Re: Cryptography : is it me ???

    Quote Originally Posted by fullmetalcoder View Post
    My understanding was that the only way to break the code was a brute-force attack which would be very long...
    There are three conditions which must be met:
    • the key must be random,
    • the key must be used only once,
    • the key must have the same length as the message

    If all of them are met, this encryption scheme is unbreakable (as proved by Shannon), otherwise it's unsecure.

    Quote Originally Posted by fullmetalcoder View Post
    Jacek and you keep talking about "known plain-text attack" but I don't really see what you mean here... I view cryptography as a way to hide data using a key and not to hide a key in know data...
    I know it sounds weird, but suppose that you send several messages that were encrypted using the same key and one of them was compromised. The attacker has a plain text and cipher text of one of the messages and he can perform a know plain-text attack on the cipher to retrieve the key and decipher the rest of messages.

    Such attack is also possible if you can guess the contents of plain-text (or part of it). In case of XOR-cipher, each correct guess gives you one character of the key.

    Get a copy of Schneier's Applied Crypthography or try this: http://www.cacr.math.uwaterloo.ca/hac/ (just beware, that this one requires a lot of courage as it has been written by mathematicians for mathematicians).

  12. #12
    Join Date
    Jan 2006
    Location
    Warsaw, Poland
    Posts
    5,372
    Thanks
    28
    Thanked 976 Times in 912 Posts
    Qt products
    Qt3 Qt4
    Platforms
    Unix/X11 Windows

    Default Re: Cryptography : is it me ???

    Quote Originally Posted by fullmetalcoder View Post
    Your mission, if you accept it, is to decrypt this file before next Sunday and to tell me which key I used...
    Next Sunday? Oh... sorry, I haven't noticed "next". :P

    The decrypted file is quite long, so I won't attach it, but it looks like this:
    Qt Code:
    1. /****************************************************************************
    2. ** Resource object code
    3. **
    4. ** Created: Fri Feb 23 22:00:14 2007
    5. ** by: The Resource Compiler for Qt version 4.2.2
    6. **
    7. ** WARNING! All changes made in this file will be lost!
    8. *****************************************************************************/
    9.  
    10. #include <QtCore/qglobal.h>
    11. ...
    12. Q_CONSTRUCTOR_FUNCTION(qInitResources_Edyuk)
    13. int qCleanupResources_Edyuk()
    14. {
    15. extern bool qUnregisterResourceData(int, const unsigned char *, const unsigned char *, const unsigned char *);
    16. qUnregisterResourceData(0x01, qt_resource_struct, qt_resource_name, qt_resource_data);
    17. return 1;
    18. }
    19. Q_DESTRUCTOR_FUNCTION(qCleanupResources_Edyuk)
    To copy to clipboard, switch view to plain text mode 
    The key is: ?10w?weak?

  13. #13
    Join Date
    Jan 2006
    Location
    travelling
    Posts
    1,116
    Thanks
    8
    Thanked 127 Times in 121 Posts
    Qt products
    Qt4
    Platforms
    Unix/X11 Windows

    Default Re: Cryptography : is it me ???

    Quote Originally Posted by jacek View Post
    There are three conditions which must be met:
    • the key must be random,
    • the key must be used only once,
    • the key must have the same length as the message
    If all of them are met, this encryption scheme is unbreakable (as proved by Shannon), otherwise it's unsecure.
    The first two conditions can be met with proper software. It only needs a random key generator owned by both sender and receiver and initialized with common data so that the sequence of random key is the same under both computers. I guess this can be done but then, then initial data with which the random key generator has been set up becomes the real key...

    About the third condition : a key with the exact same length as the message sounds quite weird and even though Shannon used this assumption to prove th unbreakability I'm pretty sure that as long as the key is not fully-repeated (i.e. key.size() > message.size() / 2) the unbreakability remain or at least we're very close to it....

    Besides, if the two first conditions are met, I don't think a mismatch of the third on make the encryption so weak. And, as wysota pointed out, the encrypted data doesn't need to be encrypted forever...
    Current Qt projects : QCodeEdit, RotiDeCode

  14. #14
    Join Date
    Jan 2006
    Location
    travelling
    Posts
    1,116
    Thanks
    8
    Thanked 127 Times in 121 Posts
    Qt products
    Qt4
    Platforms
    Unix/X11 Windows

    Default Re: Cryptography : is it me ???

    Quote Originally Posted by jacek View Post
    Next Sunday? Oh... sorry, I haven't noticed "next". :P

    The decrypted file is quite long, so I won't attach it, but it looks like this:
    Qt Code:
    1. /****************************************************************************
    2. ** Resource object code
    3. **
    4. ** Created: Fri Feb 23 22:00:14 2007
    5. ** by: The Resource Compiler for Qt version 4.2.2
    6. **
    7. ** WARNING! All changes made in this file will be lost!
    8. *****************************************************************************/
    9.  
    10. #include <QtCore/qglobal.h>
    11. ...
    12. Q_CONSTRUCTOR_FUNCTION(qInitResources_Edyuk)
    13. int qCleanupResources_Edyuk()
    14. {
    15. extern bool qUnregisterResourceData(int, const unsigned char *, const unsigned char *, const unsigned char *);
    16. qUnregisterResourceData(0x01, qt_resource_struct, qt_resource_name, qt_resource_data);
    17. return 1;
    18. }
    19. Q_DESTRUCTOR_FUNCTION(qCleanupResources_Edyuk)
    To copy to clipboard, switch view to plain text mode 
    The key is: ?10w?weak?
    I must admit that I'm quite impressed.... Just for my information, how much time did it take to decrypt it???
    Current Qt projects : QCodeEdit, RotiDeCode

  15. #15
    Join Date
    Jan 2006
    Location
    Warsaw, Poland
    Posts
    5,372
    Thanks
    28
    Thanked 976 Times in 912 Posts
    Qt products
    Qt3 Qt4
    Platforms
    Unix/X11 Windows

    Default Re: Cryptography : is it me ???

    Quote Originally Posted by fullmetalcoder View Post
    The first two conditions can be met with proper software. It only needs a random key generator owned by both sender and receiver and initialized with common data so that the sequence of random key is the same under both computers.
    That's how stream ciphers work.

    Quote Originally Posted by fullmetalcoder View Post
    I must admit that I'm quite impressed.... Just for my information, how much time did it take to decrypt it???
    I don't know exactly, but judging from the time of my posts it didn't take more than 30 minutes.

  16. #16
    Join Date
    Jan 2006
    Location
    travelling
    Posts
    1,116
    Thanks
    8
    Thanked 127 Times in 121 Posts
    Qt products
    Qt4
    Platforms
    Unix/X11 Windows

    Default Re: Cryptography : is it me ???

    Quote Originally Posted by jacek View Post
    That's how stream ciphers work.
    ...

    Maybe you could be a little more precise... Any link?
    Current Qt projects : QCodeEdit, RotiDeCode

  17. #17
    Join Date
    Jan 2006
    Location
    Warsaw, Poland
    Posts
    33,359
    Thanks
    3
    Thanked 5,015 Times in 4,792 Posts
    Qt products
    Qt3 Qt4 Qt5 Qt/Embedded
    Platforms
    Unix/X11 Windows Android Maemo/MeeGo
    Wiki edits
    10

    Default Re: Cryptography : is it me ???

    Quote Originally Posted by fullmetalcoder View Post
    The first two conditions can be met with proper software. It only needs a random key generator owned by both sender and receiver and initialized with common data so that the sequence of random key is the same under both computers.
    You see... there is no software that can generate real random numbers. As for using the key once - if you use ECB mode, you violate that rule on the very beginning.

    About the third condition : a key with the exact same length as the message sounds quite weird and even though Shannon used this assumption to prove th unbreakability I'm pretty sure that as long as the key is not fully-repeated (i.e. key.size() > message.size() / 2) the unbreakability remain or at least we're very close to it....
    If at least part of the key repeats, it means more than one message is encrypted with the same key, which may allow you to extract part of the original message, which might lead to compromising the whole message (often one only needs some part of the message).

    Besides, if the two first conditions are met, I don't think a mismatch of the third on make the encryption so weak.
    Actually, it's the most important of the three... The first two only make sure you end up with a good key (with an additional assumption that the cipher doesn't have weak keys).

    And, as wysota pointed out, the encrypted data doesn't need to be encrypted forever...
    That doesn't make a cipher strong. It only means the message is (or is not) protect "well enough for a particular need".

    Quote Originally Posted by jacek View Post
    Next Sunday? Oh... sorry, I haven't noticed "next". :P
    I was wondering why it takes you so long to answer the thread

    The key is: ?10w?weak?
    Seemed obvious the key would be 80 bit long "Just in case"...

    Just to theorise - I don't know exactly how Jacek broke the key, but I can make a guess at possible ways of dealing with the situation.

    Knowing the key is a multiple of 8bits, one had to checks ten possible lengths. Now we know that statistically the character "e" is the most common in english language, so it is most likely to receive collisions on it. Unfortunately use of C++ may change those statistics, so we have two possible ways of overcoming this.
    1. gather own statistics of C++ code by counting the number of occurences of each character in a large C++ code (like Qt sources, although it lacks comments).
    2. try to guess most popular characters - I'd say they are " " (space), ":" (colon), ";" (semicolon) and "{","}" (braces).

    The longer the text, the more collisions one may expect. Furthermore if the message is a C++ sourcecode, it most probably begins with a hash (#) - like in "#ifndef ..." or with a slash (/) - marking the beginnning of a comment. This gives additional insights, allowing one to try to guess the first character of the key right away. Furthermore if the following characters are asterisks (in case of the comment), then we might guess the beginning of the message is "/********************". That gives us more than the key length, so xoring the beginning of the ciphertext with assumed plaintext we receive the key. The rest is just about verifying the key by decrypting the rest of the message.

    So as you see, you might have compromised the key yourself here. Again, I don't know if that was the path Jacek took to decode the message, but it's a possible strategy.

    Another approach would be to try to find collisions at each 10th character of the data - that's where the amount of text for analysis is vital.

  18. #18
    Join Date
    Jan 2006
    Location
    Warsaw, Poland
    Posts
    5,372
    Thanks
    28
    Thanked 976 Times in 912 Posts
    Qt products
    Qt3 Qt4
    Platforms
    Unix/X11 Windows

    Default Re: Cryptography : is it me ???

    Quote Originally Posted by fullmetalcoder View Post
    Maybe you could be a little more precise... Any link?
    http://en.wikipedia.org/wiki/Stream_cipher

    Also check those books I've mentioned earlier.

  19. #19
    Join Date
    Jan 2006
    Location
    travelling
    Posts
    1,116
    Thanks
    8
    Thanked 127 Times in 121 Posts
    Qt products
    Qt4
    Platforms
    Unix/X11 Windows

    Default Re: Cryptography : is it me ???

    Quote Originally Posted by wysota View Post
    If at least part of the key repeats, it means more than one message is encrypted with the same key, which may allow you to extract part of the original message, which might lead to compromising the whole message (often one only needs some part of the message).

    Actually, it's the most important of the three... The first two only make sure you end up with a good key (with an additional assumption that the cipher doesn't have weak keys).
    OK. Does this mean that extending the key to make it as long as the message would do? I mean reusing the same key but shifted or semi-randomly bitmasked or anything else but in a way that's know to both encryption and decryption algorithm?

    Quote Originally Posted by wysota View Post
    Seemed obvious the key would be 80 bit long "Just in case"...
    I don't quite get you...

    Quote Originally Posted by wysota View Post
    Just to theorise - I don't know exactly how Jacek broke the key, but I can make a guess at possible ways of dealing with the situation.

    Knowing the key is a multiple of 8bits, one had to checks ten possible lengths. Now we know that statistically the character "e" is the most common in english language, so it is most likely to receive collisions on it. Unfortunately use of C++ may change those statistics, so we have two possible ways of overcoming this.
    1. gather own statistics of C++ code by counting the number of occurences of each character in a large C++ code (like Qt sources, although it lacks comments).
    2. try to guess most popular characters - I'd say they are " " (space), ":" (colon), ";" (semicolon) and "{","}" (braces).

    The longer the text, the more collisions one may expect. Furthermore if the message is a C++ sourcecode, it most probably begins with a hash (#) - like in "#ifndef ..." or with a slash (/) - marking the beginnning of a comment. This gives additional insights, allowing one to try to guess the first character of the key right away. Furthermore if the following characters are asterisks (in case of the comment), then we might guess the beginning of the message is "/********************". That gives us more than the key length, so xoring the beginning of the ciphertext with assumed plaintext we receive the key. The rest is just about verifying the key by decrypting the rest of the message.

    So as you see, you might have compromised the key yourself here. Again, I don't know if that was the path Jacek took to decode the message, but it's a possible strategy.

    Another approach would be to try to find collisions at each 10th character of the data - that's where the amount of text for analysis is vital.
    I know realize that the data itself was not very suited for XOR encoding...
    Honestly Jacek, would you have done it so fast without knowing that it was C++ code???
    Current Qt projects : QCodeEdit, RotiDeCode

  20. #20
    Join Date
    Jan 2006
    Location
    Warsaw, Poland
    Posts
    5,372
    Thanks
    28
    Thanked 976 Times in 912 Posts
    Qt products
    Qt3 Qt4
    Platforms
    Unix/X11 Windows

    Default Re: Cryptography : is it me ???

    Quote Originally Posted by fullmetalcoder View Post
    I mean reusing the same key but shifted or semi-randomly bitmasked or anything else but in a way that's know to both encryption and decryption algorithm?
    It could be enough.

    Quote Originally Posted by fullmetalcoder View Post
    I know realize that the data itself was not very suited for XOR encoding...
    The problem is not with data, but with the method.

    Quote Originally Posted by fullmetalcoder View Post
    Honestly Jacek, would you have done it so fast without knowing that it was C++ code???
    No.

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
Digia, Qt and their respective logos are trademarks of Digia Plc in Finland and/or other countries worldwide.