Создайте набор уникальных ключей, которые можно проверить без сохранения белого списка. - PullRequest
Новая
       37

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

0 голосов
/ 16 ноября 2018

Мне нужно создать наборы из 10 байтов уникальных идентификаторов.Эти наборы могут быть довольно большими (т. Е. 10000 значений) и проверяться устройством с ограниченной памятью на достоверность.Таким образом, кто-то вводит один из идентификаторов в устройство, и устройство должно иметь возможность определить, является ли идентификатор подлинным (сгенерированным мной).
Основной способ - сохранить в памяти устройства тот же набор идентификаторов ипроверьте по списку, но я не могу использовать всю эту память.
Второй способ, который я подумал, - использовать CRC или хеш-функцию: например, все идентификаторы, для которых CRC равен X, включены.Проблема в том, что мне нужно пройти через все возможные комбинации идентификаторов, чтобы найти те, которые дают правильный CRC.
В идеале, я хотел бы найти одну / две функции, которые работают следующим образом: 

 uint8_t * generate_ID(uint16_t index);
 bool is_valid validate_key(uint8_t * ID);
 //optional
 uint16_t index find_index(uint8_t * ID);

 //example
 //generate id value from index 0
 uint8_t ID[10] = generate_ID(0)
 //id is now {0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x0e, 0x0d, 0x0c, 0x0b}

 bool is_valid = validate_key(ID);
 //is_valid is True
 uint16_t index = find_index(ID);
 //index is now 0
 ID[0] = 0xff; //change ID with random value
 is_valid = validate_key(ID);
 //is_valid is now False

 //BONUS: use also a "seed" value, so that I can differentiate through sets of ids:
 uint8_t * generate_ID(uint16_t index, uint16_t seed);
 bool is_valid validate_key(uint8_t * ID, uint16_t seed);

find_index () является необязательным, потому что, как только я узнаю, что ключ действителен, я могу просто перебрать все индексы, чтобы найти соответствующий индекс.
По сути, функция generate_ID () должна быть достаточно сложной, чтобы ее было нелегкоможно предположить, если не знать приличного количества идентификатора, но можно вычислить на встроенном процессоре с ограниченной мощностью (Cortex M0)

Ответы [ 2 ]

0 голосов
/ 21 ноября 2018

Один очень простой способ сделать это с помощью модульного мультипликативного обратного, как я опишу в своем блоге здесь: http://blog.mischel.com/2017/06/20/how-to-generate-random-looking-keys/.

Идея состоит в том, что вы отображаете числа от 1 до некоторого числа x, чтобы каждое число генерировало уникальное значение в этом же диапазоне. Так, например, сопоставление может быть: 

1 -> 9875
2 -> 362
3 -> 5247
...

Это обратимый расчет. Так что если f (1) => 9875, то g (9875) => 1.

В коде, показанном в сообщении в блоге, вы можете изменить отображение, изменив значения x и m.

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

Итак, для вашей проверки установите m на очень большое число. Установите x соответственно, предпочтительно простое число больше m. Сгенерируйте первые 10000 ключей, используя эти значения. На устройстве, которое должно проверять эти числа, просто введите значения x и m и максимальный индекс (т. Е. 10 000).

Таким образом, пользователь вводит ключ, который ему дали. Вы запускаете обратную генерацию ключа и получаете число от 1 до 10000. Вы знаете, что номер действителен. Если ваш обратный расчет возвращает число, которое меньше 1 или больше 10 000, этот ключ недействителен.

Вы можете расширить это на несколько устройств, просто указав каждому устройству начальные и конечные значения, которые оно считает действительными. Расчет обратного ключа одинаков, независимо.

Эта техника обеспечивает уникальность. Безопасность ... в основном через безвестность. Если кто-то знает используемый алгоритм, включая значения x и m, и знает диапазон чисел, которые устройство должно принимать, то он может сгенерировать ключи, чтобы победить систему. Является ли это проблемой - это то, на что только вы можете ответить. Каков риск того, что кто-то попытается победить вашу систему, и какова цена, если он добьется успеха?

0 голосов
/ 17 ноября 2018

10-байтового ключа недостаточно для обеспечения безопасности.

Вам нужна безопасная хеш-функция, такая как SHA2-256, длина которой составляет 32 байта. SHA2 может быть легко реализован на большинстве систем.

Вашему ключу нужны две части: 

[text + hash]

Первая часть похожа на «имя пользователя», а вторая часть похожа на «пароль»

Вам также нужен "секретный ключ". Этот ключ представляет собой массив байтов, который хранится в вашем программном обеспечении. Затем вы добавляете «секретный ключ» к своему «имени пользователя». Найдите хэш SHA2 для полученной строки. Теперь у вас есть вывод, который является длиной исходного текста + 32 байта для хеша.

Вы можете использовать этот ключ в качестве уникального проверяемого идентификатора.

Чтобы проверить подлинность ключа, примите участие в разделе «имя пользователя» и добавьте свой секретный ключ. Возьмите SHA2 этой строки, результат должен соответствовать «паролю»

Если секретность и уникальность не являются большой проблемой, тогда вы можете использовать MD5, чей вывод составляет 16 байтов. Измените обычный текст на двоичный, чтобы он мог хранить больше информации в меньшем количестве байтов, и ваш конечный ключ будет только 20 байтов. Вы можете сократить это немного больше, но сокращение до 10 байтов не рекомендуется.

Вот пример. Я использовал реализацию SHA2 по этой ссылке:
https://github.com/B-Con/crypto-algorithms (я не уверен, работает ли он на машине с прямым порядком байтов)

Любая реализация SHA2 должна работать. 

void sha2(BYTE* dst, const BYTE* src, int len)
{
    SHA256_CTX ctx;
    sha256_init(&ctx);
    sha256_update(&ctx, (const BYTE*)src, len);
    sha256_final(&ctx, (BYTE*)dst);
}

void create_verifiable_id(const BYTE* source, BYTE *uid)
{
    BYTE hash[32];
    sha2(hash, source, ID_SIZE);

    //combine source + hash
    memcpy(uid, source, ID_SIZE);
    memcpy(uid + ID_SIZE, hash, 32);
}

int test_verfiable_id(const BYTE *uid)
{
    BYTE hash[32];
    sha2(hash, uid, ID_SIZE);

    //hash should match the second part of uid
    return memcmp(hash, uid + ID_SIZE, 32) == 0;
}

int main(void)
{
    //use a number from 0 to 0xFFFFFFFF, store in buf (4 bytes)
    //this is the "plain text" portion
    int number = 0x12345678;
    BYTE buf[ID_SIZE];
    for(int i = 0; i < sizeof(buf); i++)
    {
        buf[i] = number & 0xFF;
        number >>= 8;
    }

    //add sha2 to "plain text" to make verifiable id
    BYTE verifiable_id[32 + ID_SIZE];
    create_verifiable_id(buf, verifiable_id);

    printf("UID as hex string:\n");
    for(int i = 0; i < 32 + ID_SIZE; i++)
        printf("%02X", verifiable_id[i] & 0xFF);
    printf("\n");

    printf("Test (should succeed): %d\n", test_verfiable_id(verifiable_id));

    //change verifiable_id and test it again
    verifiable_id[0]++;
    printf("Test (should fail): %d\n", test_verfiable_id(verifiable_id));
    return 0;
}
...