криптосюжет
Nov. 23rd, 2003 05:01 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaПридумал сюжет для криптофантастического романа или повести. Точнее, не сюжет даже, а завязку.
Сидит хакер, взламывает какую-то программу (игрушку, скажем, но необязательно). В программе есть проверка серийного номера. Он ищет то место внутри программы, где эта проверка происходит, чтобы её отключить. Находит функцию, которая получает строку серийного номера (достаточно длинного) и проверяет, является ли он правильным.
Смотрит внутрь этой функции, видит: там что-то вычисляется, странное и сложное. Разбираться, что именно, чтобы написать генератор номеров, лень, там куча каких-то битовых операций неясных в цикле. С другой стороны, никаких подвохов в виде проверки контрольной суммы вычисляющего кода, или побочных эффектов функции, или других проверок в других местах, вроде бы не видно. Обрадовавшись, что всё оказалось так просто, он быстро забивает код функции, чтобы она всегда возращала истинность проверки, готовит патч, перепроверяет с ним — вроде бы всё работает, программа принимает любой серийный номер без проблем — и отсылает патч по стандартным своим каналам дистрибуции. Работа сделана.
Но что-то продолжает его беспокоить, почему-то он всё время возвращается мысленно к коду этой функции. Что-то там было знакомое, хоть даже и в ассемблере... В конце концов через пару дней он открывает опять пропущенный через дизассемблер код программы, находит эту функцию, читает внимательно, тщательно выписывает, что она делает с серийным номером, мучительно пытается вспомнить, где он это видел. Наконец срывается с места, прыгает к книжной полке, хватает изрядно потрёпанное второе издание Applied Cryptography и быстро находит в нём обсуждение MD5. Да, не может быть никаких сомнений! Загадочная функция проверки серийного номера попросту пропускает его через MD5, и сравнивает после этого с фиксированным 128-битным числом. Более того, числом этим оказывается 0x0123456789ABCDEFFEDCBA9876543210 . Герой откладывает книгу в сторону и надолго задумывается, облокотившись на клавиатуру и уставив невидящий взгляд в горящие на мониторе строки ассемблерных команд, составляющих функцию проверки серийного номера...
Сидит хакер, взламывает какую-то программу (игрушку, скажем, но необязательно). В программе есть проверка серийного номера. Он ищет то место внутри программы, где эта проверка происходит, чтобы её отключить. Находит функцию, которая получает строку серийного номера (достаточно длинного) и проверяет, является ли он правильным.
Смотрит внутрь этой функции, видит: там что-то вычисляется, странное и сложное. Разбираться, что именно, чтобы написать генератор номеров, лень, там куча каких-то битовых операций неясных в цикле. С другой стороны, никаких подвохов в виде проверки контрольной суммы вычисляющего кода, или побочных эффектов функции, или других проверок в других местах, вроде бы не видно. Обрадовавшись, что всё оказалось так просто, он быстро забивает код функции, чтобы она всегда возращала истинность проверки, готовит патч, перепроверяет с ним — вроде бы всё работает, программа принимает любой серийный номер без проблем — и отсылает патч по стандартным своим каналам дистрибуции. Работа сделана.
Но что-то продолжает его беспокоить, почему-то он всё время возвращается мысленно к коду этой функции. Что-то там было знакомое, хоть даже и в ассемблере... В конце концов через пару дней он открывает опять пропущенный через дизассемблер код программы, находит эту функцию, читает внимательно, тщательно выписывает, что она делает с серийным номером, мучительно пытается вспомнить, где он это видел. Наконец срывается с места, прыгает к книжной полке, хватает изрядно потрёпанное второе издание Applied Cryptography и быстро находит в нём обсуждение MD5. Да, не может быть никаких сомнений! Загадочная функция проверки серийного номера попросту пропускает его через MD5, и сравнивает после этого с фиксированным 128-битным числом. Более того, числом этим оказывается 0x0123456789ABCDEFFEDCBA9876543210 . Герой откладывает книгу в сторону и надолго задумывается, облокотившись на клавиатуру и уставив невидящий взгляд в горящие на мониторе строки ассемблерных команд, составляющих функцию проверки серийного номера...
no subject
Date: 2003-11-23 08:53 am (UTC)no subject
Date: 2003-11-23 08:56 am (UTC)no subject
Date: 2003-11-23 09:05 am (UTC)no subject
Date: 2003-11-23 09:20 am (UTC)no subject
Date: 2003-11-23 10:37 am (UTC)no subject
Date: 2003-11-23 10:38 am (UTC)no subject
Date: 2003-11-23 11:28 am (UTC)no subject
Date: 2003-11-23 11:30 am (UTC)no subject
Date: 2003-11-23 12:03 pm (UTC)no subject
Date: 2003-11-23 12:10 pm (UTC)For crying out loud, what difference does it make? Call it a 128-bit string, call it a sequence of 4 32-bit numbers, call it a string of 32 hex digits... who cares? What's this obsession over splitting hairs here?
no subject
Date: 2003-11-23 12:43 pm (UTC), demonstrating. It is not a coincedence that the quotation, given by you, has a "fingerprint" or "message digest" but not a "string"."The output of the algorithm is a set of four 32-bit blocks, which concatenate to form of a single 128-bit value."
- Bruce Shneier, Applied Cryptography, Second Edition, p. 436.
And, btw, 32 hex digits is a 256-bits string value, not a 128-bits one.
I have no idea on what a crying out loud reasons my remark made such an ambigous reaction but my apologies for whatever it was and take it easy.
no subject
Date: 2003-11-23 12:52 pm (UTC)Not really.
"Output block of MD5 - тоже строка, а не число" is just a funny blunder
No, it really isn't.
"The output of the algorithm is a set of four 32-bit blocks, which concatenate to form of a single 128-bit value."
These blocks and the resulting 128-bit value are binary strings, not numbers in the standard binary notation. You concatenate strings, not numbers. Numbers expressed in the standard binary notation don't allow for leading zeroes, whereas in those 32-bit blocks and in the resulting 128-bit value there may well be leading zeroes, and those leading zeroes are preserved during concatenation.
And, btw, 32 hex digits is a 256-bits string value, not a 128-bits one.
Sure you don't want to reconsider this statement?
no subject
Date: 2003-11-23 01:07 pm (UTC)Really. Each element of a string may not be equal to 8 bits exactly.
No, it really isn't.
Yes, it is. Sorry.
These blocks and the resulting 128-bit value are binary strings, not numbers in the standard binary notation. You concatenate strings, not numbers. Numbers expressed in the standard binary notation don't allow for leading zeroes, whereas in those 32-bit blocks and in the resulting 128-bit value there may well be leading zeroes, and those leading zeroes are preserved during concatenation.
May I drop a comment on a 'leading zeros' and just refer you to usage of additive constants and shift steps?
Sure you don't want to reconsider this statement?
Sure indeed :) There is a tip: a hex digit and a hex number are not the same.
no subject
Date: 2003-11-23 01:46 pm (UTC)Huh? You're not making any sense.
May I drop a comment on a 'leading zeros' and just refer you to usage of additive constants and shift steps?
Schneier didn't write about shift steps, he wrote about concatenation, a string operation.
Sure indeed :) There is a tip: a hex digit and a hex number are not the same.
Ugh. 32 hex digits carry 128 binary digits of information, which can be expressed as a 128-bit binary string, potentially with leading zeroes, or as an N-bit standard binary numeral, where N<=128. Nobody cares that, considered as an ASCII strings, those 32 hex digits take up 256 bits in an encoded ASCII form. It doesn't matter and is not interesting (and would be wrong were we to use a different character encoding, with 7 bits per character, for example).
There's no such thing as a "hex number" anyway; numbers are just numbers, they may be expressed as strings of decimal digits or binary digits or whatever, but they remain numbers just the same. Normally, a "binary number" is inexact but convenient shorthand for the standard binary representation of a number - a binary numeral - which has no leading zeroes; whereas a "binary string" is just an arbitrary sequence of binary digits, possibly with leading zeroes. As it happens, the kinds of operations performed during the computation of an MD5 digest, as well as the arrangement of its output, are much easier to conceptualize if one thinks of 32-bit binary strings and a resulting 128-bit binary string, rather than binary numerals. This is because thinking of them as binary strings makes it easy to visualize bitwise operations on all digits at once, without having to pad the smaller value with leading zeroes and then remove them after the operation is performed; it also makes it possible to speak of concatenation in its intuitively obvious sense. That's why both the RFC and Schneier discuss MD5 in terms of binary strings rather than binary numerals. The actual operations are performed on numbers anyway, and not on either strings or numerals.
Now, what should have been painfully obvious to you, and what should have spared us this tedious exchange, is the realization that binary strings and binary numerals are two obviously isomorphic and equivalent ways of representing a number with a bunch of binary digits. "0010" is the same as "10" if we want to represent the number 2 in binary. The only difference between them is the absence of leading zeroes in binary numerals, whereas leading zeroes are allowed in binary strings. Therefore it just doesn't matter. You can say that 0x0123456789ABCDEFFEDCBA9876543210 is a (more exactly, expresses a) 128-bit binary string, or you can say that it's a (expresses a) 121-bit binary numeral; if you're feeling really perverse, you can even look at it as a sequence of 34 ASCII characters. It doesn't matter. In the same way, the output of MD5 is a 128-bit binary string, or an N-bit binary numeral with N<=128, or you can say that it's customarily written with 32 hex digits that take up 256 bits in the ASCII encoding. Who cares? No sane person does. Since it's easiest to visualize the output of MD5 as a 128-bit binary string, that's what people usually call it (except some of them are calling it a 128-bit number in an abuse of notation, which is just as fine anyway, as it doesn't lead to confusion).
no subject
Date: 2003-11-23 02:58 pm (UTC)Huh? You're not making any sense.
Does Unicode rings some bells? Do a homework: how much it takes for a single element of an Unicode string?
Schneier didn't write about shift steps, he wrote about concatenation, a string operation.
"If Mj represents the jth sub-block of the message (from 0 to 15), and <<<s represents a left circular shift of s bits, the four operations are:"
- Bruce Schneier, Applied Cryptography, Second Edition, p. 437
Ugh. 32 hex digits carry 128 binary digits of information
Blah-blah-blah. 32 hex digits is a 32-bytes long string and 32 bytes represents 256 bits of information. Follow the finger: 0xF is a hex digit and a hex number; 0xFF is a hex number but not a hex digit; 0xFF02 is a hex number but not a hex digit.
There is another homework: please clarify for yourself a difference between an actual result and its representation. Please do the both homeworks before you'll start practice your lecturer's abilities next time. No offence.
Look, I really appreciated your attempts to keep a face even on such silly issue but it is getting quite boring. I do cryptography for a living and teaching is out of my bent. So let it go. Period.
no subject
Date: 2003-11-23 03:10 pm (UTC)Now this is really it. Sorry again.
no subject
Date: 2003-11-23 03:24 pm (UTC)There is no such thing as a Unicode string. There're different representations of Unicode codepoints and sequences thereof, such as UCS-2, UCS-4, UTF-8, UTF-7 etc. In some of them, every Unicode codepoint (not an "element") takes up a constant number of bits, in others a variable number.
Man, you really seem to have a problem distinguishing between abstract entities and symbolic representations. You are evidently unable to distinguish between a number and its binary representation, and now it turns out you don't understand Unicode either.
32 hex digits is a 32-bytes long string and 32 bytes represents 256 bits of information.
Do you even know what a digit is? Can you distinguish between a digit and its ASCII encoding in which it takes up one byte? Nah, didn't think so.
Maybe you could look it up in a dictionary or something. I doubt that'd solve your problems, but hey, you never know.
Follow the finger: 0xF is a hex digit and a hex number; 0xFF is a hex number but not a hex digit; 0xFF02 is a hex number but not a hex digit.
There's no such thing as a hex number, silly. Read my last comment again, and if you still don't get it, read... oh, I dunno, any really basic introductory textbook of programming that carefully explains to a student the concept of binary/decimal/hexadecimal notation might do.
I do cryptography for a living
I really sympathize. Honestly.
no subject
Date: 2003-11-23 03:30 pm (UTC):)))
Удачи.
no subject
Date: 2003-11-23 03:34 pm (UTC)