Question:
Fonction de hachage simple à implémenter sur un microcontrôleur
alexbb
2013-09-04 20:45:43 UTC
view on stackexchange narkive permalink

Je recherche une fonction de hachage très simple à implémenter sur un microcontrôleur. Le microcontrôleur affiche un identifiant de session alphanumérique à 4 chiffres sur un écran. Je veux donner un compte à la fonction de hachage et récupérer un nombre, qui sera plus tard transformé en un nombre alphanumérique à 4 chiffres. Des suggestions pour une fonction de hachage légère?

Cela pourrait être mieux adapté à Security SE. En attendant, doit-il être sécurisé cryptographiquement?
N'a pas besoin d'être sécurisé cryptographiquement, juste léger.
Quelle est la plage des valeurs d'entrée "count"? Pourquoi ne pas simplement utiliser la valeur d'entrée elle-même ... pourquoi s'embêter à la hacher?
Et le CRC16 / 32?
La valeur de comptage est un nombre que je souhaite garder privé. Rien de mauvais ne se produira s'il est découvert, mais c'est juste du point de vue de la convivialité que je ne veux pas qu'il soit montré. À propos de CRC, je n'y ai jamais pensé, cela semble être une bonne option.
Quel est le micro? Certains ont un périphérique matériel CRC sur puce, qui est à peu près aussi léger que possible.
Le micro est un MSP430, mais je viens de me dire que ce n'est pas une bonne idée d'utiliser le module CRC, car le micro pourrait traiter des messages en même temps en utilisant le module CRC.
@Polynomial il semble bien se porter ici aussi, va attendre toute migration.
@Kortuk Comme il n'a pas d'exigences de sécurité, je suis d'accord. S'il avait fallu une sécurité cryptographique, la migration aurait été une bonne idée.
@Polynomial J'ai dû faire de la sécurité cryptographique pour le travail, j'ai l'impression qu'il pourrait y avoir un chevauchement, mais s'il devait être sécurisé cryptographiquement et que je n'avais aucune expérience, je paierais une consultation. :)
@Kortuk Alors vous êtes un bon gars. Malheureusement, beaucoup de gens essaient simplement de "coller quelque chose ensemble" et de produire de la sauce faible, en particulier dans les systèmes embarqués où tout le truc "personne ne désossera jamais le micrologiciel de mon micro" entre en jeu. Cela me maintient dans un emploi, mais crée également beaucoup de problèmes pour tout le monde.
Cinq réponses:
#1
+7
Polynomial
2013-09-04 20:51:16 UTC
view on stackexchange narkive permalink

CRC32 ferait l'affaire si vous n'avez pas besoin de sécurité cryptographique. Il vous donne une valeur de sortie 32 bits et ne nécessite que des opérations simples. De nombreuses implémentations sont également disponibles pour la plupart des grandes micro-familles. Divisez en 4 octets et faites un module sur un alphabet de 32 caractères (1-9 A-Z, en sautant quelques caractères comme I et J) pour chacun, et voici votre code.

Je vais l'appuyer - CRC32 est un bon choix. Il a d'excellentes propriétés de non-collision et vous pouvez épargner la mémoire pour une LUT de 256 octets, si elle peut être implémentée en quelques décalages, et XOR et une recherche de table pour chaque octet d'entrée.
Les propriétés de détection d'erreurs du CRC interviennent uniquement lorsque la distance de frappe est suffisamment faible.Ce n'est donc pas optimal pour le hachage général (il existe des alternatives plus rapides avec une meilleure pseudo-aléatoire).Mais si les messages d'OP sont suffisamment petits, CRC-16 pourrait être idéal pour son affichage à 4 chiffres.
#2
+5
supercat
2013-09-04 21:21:22 UTC
view on stackexchange narkive permalink

Dans quelle mesure voulez-vous que cette chose soit sécurisée et quelle est la taille de votre code par rapport aux compromis d'espace? Allez-vous avoir besoin uniquement de nombres séquentiels ou de valeurs dans une séquence arbitraire?

Deux approches simples de génération de hachage sont: // Obtenir un bit aléatoire via un générateur congruentiel linéaire: int random_bit1 (void) {static unsigned longue graine; graine = graine * magicConstant + 12345; retour (graine >> 31); // Utilisez le bit supérieur - pas le bit inférieur! }

  int random_bit2 (void) {// Obtient un bit 'aléatoire' via un registre à décalage linéaire non signé avec un long shifter; if (! shifter) shifter = 1; else if (shifter & 1) shifter = (shifter>>1); else shifter = (shifter>>1); return (shifter & 1);}  

Pour générer un nombre à quatre chiffres, utilisez quelque chose comme ce qui suit:

  int result = 0; int i; for (i = 0; i<30; i ++) // Plus le nombre est élevé, moins les résultats sont biaisés {result * = 2; si (résultat > = 10000) résultat - = 10000; result + = randomBit ();}  

Notez que les deux algorithmes de génération de bits ci-dessus peuvent être adaptés pour renvoyer la nième valeur pour tout n arbitraire dans un laps de temps raisonnable, bien que le code pour faire cela sera un peu plus compliqué. D'un autre côté, aucun des deux algorithmes ne sera difficile à rétroconcevoir.

Si vous n'avez besoin que de valeurs en séquence (ce qui signifie qu'après avoir produit la nième chose, vous n'aurez jamais besoin pour produire n'importe quelle chose de numéro inférieur, et cela ne vous dérangera pas si le calcul d'une chose de numéro plus élevé nécessite le calcul de toutes les valeurs intermédiaires), il est possible de renforcer la sécurité en utilisant environ six générateurs de bits pseudo-aléatoires indépendants (peut-être shift registres avec des périodes différentes), puis utilisez quelque chose comme:

  int reallyrandombit (void) {if (randombit1 ()) {if (randombit2 ()) return randombit3 (); sinon retourner randombit4 (); } else {if (randombit3 ())
retourne randombit5 (); sinon retourner randombit6 (); }}  

Notez que pour de bons résultats, il devrait y avoir un certain mélange de la façon dont les générateurs aléatoires sont utilisés (notez que random3 est utilisé à deux endroits différents) mais il faut éviter les chemins de rétroaction (aucun des les générateurs aléatoires affectent le déplacement de tout ce qui l'affecterait) à moins que l'on ne dispose des outils pour les analyser complètement.

#3
+5
Rev1.0
2013-09-05 12:42:21 UTC
view on stackexchange narkive permalink

Vous pourriez être intéressé par cette bibliothèque Crypto. Il est publié sous la GPL v3.

Crypto-avr-lib est un ensemble d'implémentations de différentes primitives cryptographiques. En raison des limitations particulières des microcontrôleurs (très peu d'espace, la RAM et la mémoire flash vont de quelques octets à quelques Kio), la référence ou les implémentations optimisées «normales» ne sont pas utilisables. Par conséquent, nous essayons de fournir des implémentations spéciales qui respectent les ressources extrêmement limitées des applications de microcontrôleur.

Il existe plusieurs algorithmes de hachage disponibles:

  • Blake
  • BlueMidnightWish
  • Grøstl
  • MD5
  • SHA-256
  • SHA-1
  • SHA-3 (Keccak)
  • SHABAL
  • Skein
  • Twister
  • Whirlpool

Vous pouvez accéder au code complet via leur référentiel Subversion à http://das-labor.org/svn/microcontroller-2/crypto-lib.

Beaucoup exagéré.OP a un affichage à 4 chiffres.Et ces hachages cryptographiques sont nettement plus lents que même un MurmurHash3 (qui est sans doute lent pour un microcontrôleur en raison de l'utilisation de la multiplication)
@bryc: Vrai, mais pourrait être intéressant pour les autres de toute façon.
#4
+3
Rocketmagnet
2013-09-05 02:14:46 UTC
view on stackexchange narkive permalink
  • Si vous ne vous souciez vraiment pas de la sécurité
  • Si tout ce que vous voulez faire est de «gâcher» un nombre

Alors il y a un un tas de façons très simples de faire cela, voici deux auxquelles je peux penser:

  void really_simple_hash (uint16_t x) {SWAP_NIBBLES (FIRST_BYTE (x)); SWAP_NIBBLES (SECOND_BYTE (x)); x ^ = 0xAAAA; return x;}  

Sur un PIC18, cela se traduit par du code très simple:

  SWAPF x, fSWAPF x + 1, fmovlw 0xAAxorwf x, fxorwf x +1, f  

C'est assez léger à seulement 5uS de temps d'exécution sur un PIC18 fonctionnant à 10MIPS. Si cela ne suffit pas, vous pouvez mélanger les bits dans le nombre. Encore une fois, sur un PIC18:

  rrcf x, f; Ensuite, nous prenons chaque bit du mot sourcerlcf y + 1, f; et déplacez-le dans l'un des octets de destinationrrcf x + 1, frlcf y, f; Il y a: rrcf x, f; - huit décalages à droite de x, rlcf y + 1, f; - huit décalages à droite de x + 1, rrcf x + 1, f; - huit décalages à gauche de y, rlcf y + 1, f; - huit décalages à gauche de y + 1, rrcf x, frlcf y, f; Vous pouvez les faire dans l'ordre de votre choix: rrcf x + 1, frlcf y, frrcf x, frlcf y + 1, frrcf x, frlcf y, frrcf x, frlcf y, frrcf x, f rlcf y + 1, f rrcf x + 1 , frlcf y, frrcf x, frlcf y + 1, frrcf x + 1, frlcf y + 1, frrcf x, frlcf y, frrcf x + 1, frlcf y, frrcf x, frlcf y + 1, frrcf x, frlcf y, frrcf x, frlcf y, f; Enfin, le résultat est stocké dans y  

C'est encore assez léger, avec un temps d'exécution de seulement 37uS pour ce même PIC18.

#5
+1
jippie
2013-09-04 21:37:05 UTC
view on stackexchange narkive permalink

Si elle n'a pas besoin d'être cryptographique forte:

  • choisissez une clé aléatoire de même longueur en bits;
  • partager la clé entre l'expéditeur et le destinataire;
  • expéditeur -side: crypto-text = clé EOR en texte clair (vous pouvez faire cet octet par octet ).

Facultatif:

  • receiver -side clear-text = crypto-text EOR key.
L'OP ne veut pas crypter un message, il a juste besoin d'une simple fonction de hachage. Il n'y a ni «expéditeur» ni «destinataire». Je ne pense pas que cette réponse aide du tout.
Alors sautez le côté récepteur et utilisez le texte crypté comme hachage. Un hachage a généralement la propriété de ne pas pouvoir être inversé en texte clair d'origine, mais je ne pense pas que l'OP s'en souciera.
De plus, les hachages transforment une source de longueur variable en un hachage de taille fixe.


Ce Q&R a été automatiquement traduit de la langue anglaise.Le contenu original est disponible sur stackexchange, que nous remercions pour la licence cc by-sa 3.0 sous laquelle il est distribué.
Loading...