взломщикам RSA на заметку

Тема в разделе "WASM.CRYPTO", создана пользователем RElf, 19 мар 2008.

  1. georgel

    georgel New Member

    Публикаций:
    0
    Регистрация:
    4 ноя 2006
    Сообщения:
    19
    Привет. Попал на непонятную мне реализацию RSA. Есть дос файлик реализующий как буд-то выход = вход ^ 3 mod k. При специально подставленных малых значениях вроде все работает...В архиве (пароль wasmwasm) здесь:

    http://files.onlinesoft.ru/cgi-bin/filex.cgi?ac-go=r.rar

    есть и c++ аналог дос файлика. Длина чисел - 192 байта. К ключу вначале есть и не очень понятная константа 77, которая (как я думаю) имеет строго определенное значение в зависимости от младшего байта ключа (b9).

    Нуждаюсь в помощи понятия алгоритма (пока даже не смею верить, что возможно найти приватную експоненту)...Спасибо.
     
  2. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    RSA может использовать двухбитные экспоненты 3,17,257 или 65537, все одно.
    Это сделано исключительно для быстродействия, а так все экспоненты одинаковы по стойкости.

    Если прога не добавляет к старшим разрядам входа случайных чисел, то некоторая уязвимость типа выбранный текст существует - читаем брюса шнаера.

    А ежели прога добавляет-таки в начало мусор - то никак.
     
  3. georgel

    georgel New Member

    Публикаций:
    0
    Регистрация:
    4 ноя 2006
    Сообщения:
    19
    persicum
    Ничего прога не добавляет. В примере есть реальные данные (посмотрите на выходной файл). Могу извлечь несколько "правильных" входных файлов. С модулем К не могу разобраться перед тем как вообще думать об уязвимости...
     
  4. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.152
    georgel
    возьми нормальную реализацию с sourceforge.net
     
  5. georgel

    georgel New Member

    Публикаций:
    0
    Регистрация:
    4 ноя 2006
    Сообщения:
    19
    UbIvItS
    Tы меня не правильно понял - суть сделать свой входной файл для этого алгоритма :dntknw:
     
  6. Ruptor

    Ruptor Marcos el Ruptor

    Публикаций:
    0
    Регистрация:
    9 янв 2005
    Сообщения:
    167
    Адрес:
    Australia
    georgel

    Sounds like an 8-bit Montgomery RSA signature implementation. That constant multiplied by the first byte of the modulus should give 0xFF. You have three choices: 1) factor that 1536-bit modulus (most expensive), 2) find a large number of smooth signatures and from them build a table of signatures of all small primes, then build signatures by factoring the data you need to sign, with some luck you'll have a smooth enough meaningful input file (much cheaper) or 3) since it's a simple cube without hashing, you can prepare special kind of files with matching signatures: all-0 or a small number that taken to the power of 3 will give you the right signature (super cheap). You'll just have to convert them to n-residue format. Shamus Miracl library has a function for that. There is not much else you can do.
     
  7. georgel

    georgel New Member

    Публикаций:
    0
    Регистрация:
    4 ноя 2006
    Сообщения:
    19
    deleted
     
  8. georgel

    georgel New Member

    Публикаций:
    0
    Регистрация:
    4 ноя 2006
    Сообщения:
    19
    Ruptor
    Thank you for your competent directions. Could you tell me what is so specific about this Montgomery implementation that I am unable to achieve the same results while using a big number calculator? I suspect there is something very tricky about the modulus. And sorry for even mentioning it but don't you think I have a chance to find a private exponent by mere bruteforcing (in case it is a relatively low number)?

    Option 3) is not an option actually since every byte in the message counts :dntknw:
     
  9. Ruptor

    Ruptor Marcos el Ruptor

    Публикаций:
    0
    Регистрация:
    9 янв 2005
    Сообщения:
    167
    Адрес:
    Australia
    You must convert the input number to n-residue format. Looks like that conversion is missing in the code. The final conversion may also be missing. There is nothing special about the modulus.

    And no, you don't have a chance of finding the private exponent. It will not be a low number.
     
  10. georgel

    georgel New Member

    Публикаций:
    0
    Регистрация:
    4 ноя 2006
    Сообщения:
    19
    Ruptor
    Added: I've experimented with the given input (which appears to be in n-residue format) and failed with the big number calculator! Why?

    Since the input is prepared by the party that holds the private exponent there is no access to the code that makes this conversion...Although an access to another obfuscated code that makes similar conversion in the field might be possible it would use the same algo and same public exponent =3 but with shorter (and different) key...So I think it is irrelevant to this problem...

    No, the output is directly used for checksum and string comparison.

    Last hope disappeared. I still wonder (because of my ignorance) how such super large exponents are actually used :)
     
  11. Ra_

    Ra_ New Member

    Публикаций:
    0
    Регистрация:
    4 мар 2007
    Сообщения:
    289
  12. Ruptor

    Ruptor Marcos el Ruptor

    Публикаций:
    0
    Регистрация:
    9 янв 2005
    Сообщения:
    167
    Адрес:
    Australia
    georgel

    You failed with the big number calculator probably because big number calculators operate with normal numbers, and if they support n-residue format, those are most probably n-residues mod 2^32, and yours is mod 2^8. You may also have to try converting the result back to binary and not converting it to see which one of the two it is, but it should work.

    There is plenty of hope. They are exponentiating the input itself, not its hash. You can easily find plenty of smooth cubes to be able to reproduce a signature maybe not for any, but at least for any reasonably smooth input. It's not as hard as factoring the modulus.
     
  13. Ra_

    Ra_ New Member

    Публикаций:
    0
    Регистрация:
    4 мар 2007
    Сообщения:
    289
  14. georgel

    georgel New Member

    Публикаций:
    0
    Регистрация:
    4 ноя 2006
    Сообщения:
    19
    Ruptor
    The message consists of 12 AES encryptions of constants 0-b with a single key...One of them is partially overwritten with a string. Does it sound you like a reasonably smooth input?
     
  15. Ruptor

    Ruptor Marcos el Ruptor

    Публикаций:
    0
    Регистрация:
    9 янв 2005
    Сообщения:
    167
    Адрес:
    Australia
    Smooth means divisible only by small primes. So yes, it does. It can be. Try factoring it.
     
  16. georgel

    georgel New Member

    Публикаций:
    0
    Регистрация:
    4 ноя 2006
    Сообщения:
    19
    Ruptor
    What's the difference between factoring a 1536 bit modulus and a message of the same length?
     
  17. flankerx

    flankerx New Member

    Публикаций:
    0
    Регистрация:
    2 июл 2004
    Сообщения:
    423
    Адрес:
    Moscow, Russia
    georgel
    RSA modulus doesn't have small factors, it is chosen to resist factoring. Message of same length may have small factors (and it is very likely that it actually has) and may be factored much easily.
     
  18. georgel

    georgel New Member

    Публикаций:
    0
    Регистрация:
    4 ноя 2006
    Сообщения:
    19
    flankerx
    Sorry for incompetence, but what should be done with the factored message? Is there a software that is already made with which I could try to factor a message just too see if it is possible to be done and how long it takes?
     
  19. flankerx

    flankerx New Member

    Публикаций:
    0
    Регистрация:
    2 июл 2004
    Сообщения:
    423
    Адрес:
    Moscow, Russia
    You can try RSATool (which you can find on this site, http://wasm.ru/baixado.php?mode=tool&id=308)
     
  20. georgel

    georgel New Member

    Публикаций:
    0
    Регистрация:
    4 ноя 2006
    Сообщения:
    19
    flankerx
    I've tried it with the output.bin (in reversed order of bytes, of course). So far it has found the following:
    PRIME FACTOR: 2
    PRIME FACTOR: 2
    PRIME FACTOR: 3
    PRIME FACTOR: 6D
    PRIME FACTOR: 1183
    PRIME FACTOR: 757C4DF2E9D
    PRIME FACTOR: 2EB35CB6AD23

    What am I supposed to do with these primes?