Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Господа, будьте снисходительны, не бросайтесь сразу штрафовать за, как вам кажется, глупые вопросы - beginners на то и beginners.
|
Re: Подбор параметров нестандартного CRC 24.11.04 10:20 Число просмотров: 2522
Автор: leo <Леонид Юрьев> Статус: Elderman
|
Всё может быть как очень просто, так и совсем нет.
Если там действительно CRC, и тем более по полиному не более X16, то найти полином легко, даже просто brute-force. В Сети есть описание как "умных" итеративных алгоритмов, так и brute-force подбор. Если полином не длинее 16, то "подбор" IMHO будет удобнее.
Но там может быть не просто CRC, а смесь c функцией (нелинейной и/или не коррелирующей с CRC). Например можно посчитать CRC32, а потом сложить старшие и младшие 16 бит. Или взять 16 бит начитая с 3-го. Можно сделать и еще "хуже" - посчитать MD5 и взять какие-нибудь два байта из 16.
|
|
<beginners>
|
Подбор параметров нестандартного CRC 24.11.04 02:05 [leo, fly4life]
Автор: Dimik Статус: Незарегистрированный пользователь
|
Итак, суть задачи.
Есть сообщение вида 09 F8 CC FB FA EF BB 9E, последние два байта контрольная сумма. По идее это должен быть CRC, но с нестандартным полиномом, начальными и XOR константантами.
Сообщения отлавливать крайне трудно, т.к. кроме проверки по контрольной сумме есть еще проверка на адекватность сообщения, то есть если послать сообщение, которое не вписывается в формат сообщений в системе, то оно не пройдет даже при верном CRC. Тем не менее удалось наловить небольшую табличку рядомстоящих сообщений.
Нужно поиметь значения параметров для расчет этого CRC.
|
|
Re: Подбор параметров нестандартного CRC 24.11.04 10:20
Автор: leo <Леонид Юрьев> Статус: Elderman
|
Всё может быть как очень просто, так и совсем нет.
Если там действительно CRC, и тем более по полиному не более X16, то найти полином легко, даже просто brute-force. В Сети есть описание как "умных" итеративных алгоритмов, так и brute-force подбор. Если полином не длинее 16, то "подбор" IMHO будет удобнее.
Но там может быть не просто CRC, а смесь c функцией (нелинейной и/или не коррелирующей с CRC). Например можно посчитать CRC32, а потом сложить старшие и младшие 16 бит. Или взять 16 бит начитая с 3-го. Можно сделать и еще "хуже" - посчитать MD5 и взять какие-нибудь два байта из 16.
|
| |
Если там действительно CRC и есть возможность подавать на... 18.12.04 02:49
Автор: Lexy Статус: Незарегистрированный пользователь
|
Если там действительно CRC и есть возможность подавать на вход разные значения, то можно все легко вскрыть без перебора за счет линейности алгоритма. Количество необходимых тестовых значений для 16-битного CRC будет, по-видимому равно 17, для 32-битного - 33 и т.п. Общая идея такова:
Если некоторый CRC-подобный алгоритм на входах A, B, C дает F(A), F(B), F(C) соответственно, то на входе D = A^B^C он даст F(D) = F(A)^F(B)^F(C). Отсюда выбираем какое-то базовое значение A, и далее значения B_i = A ^ X_i, так чтобы X_i были линейно независимы (например, степени двойки). Вычисляем на них значения целевой функции, остальные через них легко выражаются. В интернете можно найти подробные источники по поводу таких алгоритмов.
Если же целевой алгоритм - не CRC, то имеет смысл сначала его извлечь каким-либо способом, и потом уже исследовать отдельно.
===
Lexy
|
| |
Неужели больше никто ничего не подскает? 29.11.04 10:37
Автор: Dimik Статус: Незарегистрированный пользователь
|
|
|
| |
Спасибо за ответ. 24.11.04 12:05
Автор: Dimik Статус: Незарегистрированный пользователь
|
Спасибо за ответ.
> даже просто brute-force. В Сети есть описание как "умных"
> итеративных алгоритмов, так и brute-force подбор. Если
А можно по подробнее, как такой умный алгоритм реализвать или может быть найти что-то готовое...
> полином не длинее 16, то "подбор" IMHO будет удобнее.
>
Имхо нет, т.к. у нас 16 битный полином, 16 битное начальное значение, 16 битный XOR на выходе + два бита иверсии входа и выхода. (В трактовке Painless CRC guide)
Итого (2^16(2^16)2^16)*2*2 вариантов. Если применить алгоритм произвольного CRC из того же "бозболезненного руководства по CRC", то получаем не один десяток лет перебора..... Может существуют более быстрые не табличные алгоритмы?
> Но там может быть не просто CRC, а смесь c функцией
> (нелинейной и/или не коррелирующей с CRC). Например можно
> посчитать CRC32, а потом сложить старшие и младшие 16 бит.
> Или взять 16 бит начитая с 3-го. Можно сделать и еще "хуже"
> - посчитать MD5 и взять какие-нибудь два байта из 16.
Маловероятно. Там стоит PIC процессор, который крутится на 1МГц тактовой, а значит выдает 0.25MIPS. Не думаю что те, кто писал софт под этот пик просались бы на ветер драгоценными миллисекундами.
Может быть такой вариант, что это даже и не CRC, а какой-то простой суррогатный алгоритм, порожденный бурной фантазией программеров.... =( Но как быть в таком случае, я тем более не знаю...
|
| | |
скажи чем занимается этот пик контроллер 21.12.04 12:41
Автор: Wud <Леха> Статус: Member
Отредактировано 21.12.04 12:43 Количество правок: 1
|
и возможно все очень просто...
-
и откуда ты вытянул этот пакет
|
|
|
подробно о проекте
Анализ криптографических сетевых...
