Condensat d'intégrité indépendant du format physique et du codage ?

Le
Phil l'ancien
Disons que je dois transmettre une longue liste de nombres
à un destinataire dont je ne maîtrise pas l'implémentation
(il peut avoir codé en binaire, en BCD, en n'importe quoi).

Il doit vérifier l'intégrité de la liste de nombres qu'il
a reçue. La méthode classique est de lui transmettre
un condensat de la liste de nombres (checksum, etc.),
qu'il recalcule de son côté.

Le problème, c'est que, ne connaissant pas son
implémentation, je ne peux pas utiliser les outils
qui calculent un condensat de fichier (si ça se
trouve, il a mis la liste de nombres dans une base
de données par exemple).


Je pourrais inventer un algo quelconque, mais
le problème est que je ne pourrais pas prouver
son efficacité, puisque ce serait un algo "maison".


Connaissez-vous un algo de condensat
documenté, rapide (et de puissance connue)
que je pourrais utiliser ?

Merci !
(et j'espère que ce n'est pas trop HS)


Phil l'ancien-
Questions / Réponses high-tech
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses Page 1 / 2
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
Francois Grieu
Le #571009
Dans l'article "Phil l'ancien"
Disons que je dois transmettre une longue liste de nombres
à un destinataire dont je ne maîtrise pas l'implémentation
(il peut avoir codé en binaire, en BCD, en n'importe quoi).

Il doit vérifier l'intégrité de la liste de nombres qu'il
a reçue. La méthode classique est de lui transmettre
un condensat de la liste de nombres (checksum, etc.),
qu'il recalcule de son côté.

Le problème, c'est que, ne connaissant pas son
implémentation, je ne peux pas utiliser les outils
qui calculent un condensat de fichier (si ça se
trouve, il a mis la liste de nombres dans une base
de données par exemple).


Je pourrais inventer un algo quelconque, mais
le problème est que je ne pourrais pas prouver
son efficacité, puisque ce serait un algo "maison".


Connaissez-vous un algo de condensat
documenté, rapide (et de puissance connue)
que je pourrais utiliser ?


Quelques remarques:
- si le "condensat" est une "checksum", un code à redondance
cyclique (CRC), *OU* est une valeur courte (moins de disons
50 bits) calculée par une méthode publique, il offre une
protection quasi nulle contre les attaques délibérées
consistant à changer le fichier, puisqu'il est facile de
changer un fichier sans changer le condensat.
- même absence de protection si le condensat (quelque soit sa
nature et sa taille) est calculé par une méthode publique et
transmis sans protection particulière avec le fichier, car
il est facile de changer le fichier et le condensat.
- bref pour avoir une protection, il faut un condensat calculé
selon une méthose cryptographiquement saine, et transmis dans
des conditions où son intégrité est assurée (par exemple, par
téléphone, ou mieux signé par un algorithme à clé publique).

Ceci étant posé, quand une information est transmise, elle
l'est souvent sous forme de fichier, comprenant un nombre
entier d'octets de 8 bits (parfois: multiple supérieur mais
rentant dans ce cas assez général), et à peu près tout le
monde est d'accord pour calculer le hash, par exemple SHA-1,
d'un tel fichier, SANS en connaitre le format.

Mon conseil serait donc de
- si il y a plusieurs fichiers, les rassembler en une archive
(zip, tar, tar.bz2..)
- calculer un condensat SHA-1 du fichier / de l'archive
(ou RipeMD-160, SHA-256, SHA-512, pour ceux qui ne veulent
pas entrer dans une discussion de spécialistes sur la sécurité
de SHA-1 dans les attaques de type sconde préimage)
- signer le consensat avec la clé publique de l'émetteur
- transmettre (protégé par une encapsulation adéquate) le
fichier / archive et la signature
Note: une bonne utilisation de PGP/GPG combine au moins les 3
dernières étapes de manière transparente.

Bien sur le destinataire doit vérifier la signature avant
d'utiliser le ficher / ouvrir l'archive.


François Grieu

Francois Grieu
Le #570804
Dans l'article "Phil l'ancien"
Disons que je dois transmettre une longue liste de nombres
à un destinataire dont je ne maîtrise pas l'implémentation
(il peut avoir codé en binaire, en BCD, en n'importe quoi).

Il doit vérifier l'intégrité de la liste de nombres qu'il
a reçue. La méthode classique est de lui transmettre
un condensat de la liste de nombres (checksum, etc.),
qu'il recalcule de son côté.

Le problème, c'est que, ne connaissant pas son
implémentation, je ne peux pas utiliser les outils
qui calculent un condensat de fichier (si ça se
trouve, il a mis la liste de nombres dans une base
de données par exemple).


Je pourrais inventer un algo quelconque, mais
le problème est que je ne pourrais pas prouver
son efficacité, puisque ce serait un algo "maison".


Connaissez-vous un algo de condensat
documenté, rapide (et de puissance connue)
que je pourrais utiliser ?


Quelques remarques:
- si le "condensat" est une "checksum", un code à redondance
cyclique (CRC), *OU* est une valeur courte (moins de disons
50 bits) calculée par une méthode publique, il offre une
protection quasi nulle contre les attaques délibérées
consistant à changer le fichier, puisqu'il est facile de
changer un fichier sans changer le condensat.
- même absence de protection si le condensat (quelque soit sa
nature et sa taille) est calculé par une méthode publique et
transmis sans protection particulière avec le fichier, car
il est facile de changer le fichier et le condensat.
- bref pour avoir une protection, il faut un condensat calculé
selon une méthode cryptographiquement saine, et transmis dans
des conditions où son intégrité est assurée (par exemple, par
téléphone, ou mieux signé par un algorithme à clé publique).

Ceci étant posé, quand une information est transmise, elle
l'est souvent sous forme de fichier, comprenant un nombre
entier d'octets de 8 bits (parfois: multiple supérieur mais
rentrant dans ce cas assez général), et à peu près tout le
monde est d'accord pour calculer le hash, par exemple SHA-1,
d'un tel fichier, SANS en connaitre le format.

Mon conseil serait donc de
- si il y a plusieurs fichiers, les rassembler en une archive
(zip, tar, tar.bz2..)
- calculer un condensat SHA-1 du fichier / de l'archive
(ou RipeMD-160, SHA-256, SHA-512, pour ceux qui ne veulent
pas entrer dans une discussion de spécialistes sur la
sécurité de SHA-1 dans les attaques de type seconde préimage)
- signer le consensat avec la clé privée de l'émetteur
- transmettre (protégé par une encapsulation adéquate) le
fichier / archive et la signature
Note: une bonne utilisation de PGP/GPG combine au moins les 3
dernières étapes de manière transparente.

Bien sur le destinataire doit vérifier la signature avec la
clé publique de l'émetteur avant d'utiliser le ficher / ouvrir
l'archive.


François Grieu
[re-posté avec corrections]

Phil l'ancien
Le #570803
Francois Grieu
Phil l'ancien

Le problème, c'est que, ne connaissant pas son
implémentation, je ne peux pas utiliser les outils
qui calculent un condensat de fichier (si ça se
trouve, il a mis la liste de nombres dans une base
de données par exemple).

Je pourrais inventer un algo quelconque, mais
le problème est que je ne pourrais pas prouver
son efficacité, puisque ce serait un algo "maison".

Connaissez-vous un algo de condensat
documenté, rapide (et de puissance connue)
que je pourrais utiliser ?


Quelques remarques:
- si le "condensat" est une "checksum", un code à redondance
cyclique (CRC), *OU* est une valeur courte (moins de disons
50 bits) calculée par une méthode publique, il offre une
protection quasi nulle contre les attaques délibérées
consistant à changer le fichier, puisqu'il est facile de
changer un fichier sans changer le condensat.


On est d'accord, mais dans le cas qui m'occupe,
on cherche juste à détecter une erreur de transmission
ou une corruption de données, pas à empêcher
ni détecter une altération délibérée.


- même absence de protection si le condensat (quelque soit sa
nature et sa taille) est calculé par une méthode publique et
transmis sans protection particulière avec le fichier, car
il est facile de changer le fichier et le condensat.
- bref pour avoir une protection, il faut un condensat calculé
selon une méthode cryptographiquement saine, et transmis dans
des conditions où son intégrité est assurée (par exemple, par
téléphone, ou mieux signé par un algorithme à clé publique).


Toujours d'accord, même si ça ne s'applique
pas au cas qui m'occupe.


Ceci étant posé, quand une information est transmise, elle
l'est souvent sous forme de fichier, comprenant un nombre
entier d'octets de 8 bits (parfois: multiple supérieur mais
rentrant dans ce cas assez général), et à peu près tout le
monde est d'accord pour calculer le hash, par exemple SHA-1,
d'un tel fichier, SANS en connaitre le format.



Je sais bien, mais ce n'est pas ce que je demande.
Il s'agit de détecter une erreur de transmission,
une erreur de prise en compte ou une corruption
des données (liste de nombres) ++ dans une implémentation libre ++.

On ne peut pas faire d'hypothèses sur le codage,
ni sur des fichiers, etc.


Mon conseil serait donc de
- si il y a plusieurs fichiers, les rassembler en une archive
(zip, tar, tar.bz2..)
- calculer un condensat SHA-1 du fichier / de l'archive
(ou RipeMD-160, SHA-256, SHA-512, pour ceux qui ne veulent
pas entrer dans une discussion de spécialistes sur la
sécurité de SHA-1 dans les attaques de type seconde préimage)
- signer le consensat avec la clé privée de l'émetteur
- transmettre (protégé par une encapsulation adéquate) le
fichier / archive et la signature
Note: une bonne utilisation de PGP/GPG combine au moins les 3
dernières étapes de manière transparente.
Bien sur le destinataire doit vérifier la signature avec la
clé publique de l'émetteur avant d'utiliser le ficher / ouvrir
l'archive.



Je comprend et je connais tout ça, mais ça ne
s'applique pas à ce que je demande...


Phil l'ancien-


Phil l'ancien
Le #570802
Je reformule pour être plus clair.

Disons que j'ai une liste de nombres entiers (*), que
j'ai transmise par différents moyens, éventuellement
en plusieurs fois, à des destinataires.

Chaque destinataire a donc une liste de nombres
supposée être identique à la liste de référence
(la mienne).

Chaque destinataire a son système d'information
propre, que je ne connais pas, et sa propre implémentation.
Je ne sais pas si c'est un fichier ou une base de données, etc.

Chaque destinataire, et moi-même, avons des systèmes
d'information : on est capables de compter, d'additionner,
etc.


Je cherche un algo de type checksum ou autre
qui permette à chaque destinataire de s'assurer
que sa liste est bien identique à la mienne, avec
une fiabilité connue.

Dans cette application, il n'y a pas de besoin
sur la confidentialité, l'authenticité, la falsification, etc.
Juste un risque de mauvaise transmission
ou d'erreur de prise en compte des transmissions.



Exemples d'algos possibles :

Je transmet à tous les destinataires
la longueur de la liste et la somme de tous les nombres.
(ex : 1000 nombres, somme 12345654321)
Chaque destinataire regarde la longueur de sa liste et
additionne de son côté. Si il trouve la même longueur
de liste et la même somme, il en déduit que sa liste
est correcte.

ou

On compte le nombres de '1', le nombre
de '2', etc. dans la liste de nombres
exprimés en base 10.

etc.


Connaissez-vous un algo efficace de ce type ?
(j'ai besoin d'un algo documenté en termes
de sa fiabilité, c'est à dire de la probabilité
qu'il laisse passer une ou des erreurs).


Phil l'ancien-


(*) les entiers sont bornés, et la longueur de
la liste est bornée également.
Francois Grieu
Le #570801
Dans l'article "Phil l'ancien"
Je reformule pour être plus clair.

Disons que j'ai une liste de nombres entiers (*), que
j'ai transmise par différents moyens, éventuellement
en plusieurs fois, à des destinataires.

Chaque destinataire a donc une liste de nombres
supposée être identique à la liste de référence
(la mienne).

Chaque destinataire a son système d'information
propre, que je ne connais pas, et sa propre implémentation.
Je ne sais pas si c'est un fichier ou une base de données, etc.

Chaque destinataire, et moi-même, avons des systèmes
d'information : on est capables de compter, d'additionner,
etc.


Je cherche un algo de type checksum ou autre
qui permette à chaque destinataire de s'assurer
que sa liste est bien identique à la mienne, avec
une fiabilité connue.

Dans cette application, il n'y a pas de besoin
sur la confidentialité, l'authenticité, la falsification, etc.
Juste un risque de mauvaise transmission
ou d'erreur de prise en compte des transmissions.


Ce n'est pas l'acception courante de 'intégrité' dans ce
forum de cryptographie, qui s'intéresse aux adversaires qui
modifient sciemment les données; d'où mon précédent message.


Exemples d'algos possibles :

Je transmet à tous les destinataires
la longueur de la liste et la somme de tous les nombres.
(ex : 1000 nombres, somme 12345654321)
Chaque destinataire regarde la longueur de sa liste et
additionne de son côté. Si il trouve la même longueur
de liste et la même somme, il en déduit que sa liste
est correcte.

ou

On compte le nombres de '1', le nombre
de '2', etc. dans la liste de nombres
exprimés en base 10.


Une point qui a son importance: l'ordre des entiers est-il
significatif ? Dans les techniques citées en exemple, la
permutation d'éléments de la liste n'est pas détectée.
C'est peut-être une faiblesse non voulue. Noter que dans
certains modes de transmission (photocopies, découpage en
segments de fichiers manuellement réassemblés, transmission
par internet selon le protocole UDP..) la permutation de
segments est une erreur accidentelle relativement fréquente,
éventuellement davantage que l'altération d'un chiffre.


Connaissez-vous un algo efficace de ce type ?
(j'ai besoin d'un algo documenté en termes
de sa fiabilité, c'est à dire de la probabilité
qu'il laisse passer une ou des erreurs).


Pour pouvoir garantir rigoureusement la fiabilité de la
détection d'erreur accidentelle sans connaitre du tout
le mode de de transmission, la solution radicale (et
habituelle) est d'exprimer la liste d'entiers de manière
bien définie en une suite d'octet (ou de bits), et en
général on choisi la forme sous laquelle ces informations
sont échangées; puis d'utiliser un hash cryptographique
appliqué à cette suite.
En théorie, la même technique ne fonctionne pas avec un CRC,
car on ne peut exclure que le canal de transmission ait une
forte propension à ne faire que des erreurs qui n'altèrent
par ce CRC (exemple classique: si le canal de transmission
corrige ses erreurs avec le même polynôme).

Si, comme dans votre cas, on ingore la méthode de
transmission et de stockage, on défini précisément une
transformation de la liste de nombres en une suite d'octets
(ou de bits); il y a au moins un standard, ASN-1.
Ou encore, on prend une méthode ad-hoc simple, exemple:
si on sait que chaque entier est dans l'intervalle [0..2^32-1],
on peut dire que chaque entier est représenté par 32 bits
codant sa valeur en base 2, poids fort en tête; noter que
cette convention simplifie le calcul du hash SHA-1, car pour
celui-ci on commence par regrouper les bits en entiers selon
la convention exactement inverse, de sorte que les deux
transcodages sucessifs deviennent superflus.

Je ne connais pas d'autre technique standard de valeur de
contrôle de liste d'entiers. Toutefois il me semble que l'on
peut construire un algorithme simple, travaillant directement
sur les entiers, et à résistance démontrable aux erreurs
accidentelles: on choisi comme paramètres deux nombres
premiers distincts m et n, tels que 1/n est plus petit que
la probabilité d'erreur non détectée désirée; et l'on calcule
la valeur de contrôle v des entiers aj de la liste par
v := 0
pour chaque entier aj de la liste
v := (v * m + aj) % n
On peut je crois démontrer la résistance de ceci, dans un
modèle où l'on fixe des listes en erreurs, et où n et m
sont choisis indépendemment, au hasard; on en déduit que
ça marche en pratique si m et n sont choisis d'une manière
qui est sans rapport avec le canal de transmission.
Avec m = 37, n = 56512723, et 0<=aj<56512897,
v * m + aj < 2^31 ce qui permet un calcul assez facile
dans de nombreux languages. Noter qu'il est très facile
de provoquer une collision (les listes 1,0 et 0,37 sont
en collision), pour rendre celà moins probable il faut
augmenter m, mais du coup il faut réduire n si l'on à une
limitation pratique pour le produit m*n.

Si l'ordre de la liste doit ne pas être significatif,
on peut trier la liste avant calcul de la valeur de
contrôle, mais c'est un peu lourd.

Sans tri, et à niveau d'erreur démontrable dans le sens
ci-dessus, c'est peut-être possible avec quelque chose
dans le genre (je ne promet rien)
v := 0
pour chaque entier aj de la liste
v := (v + 1 + ((aj * m) % p)) % n
avec les paramètres m n p premiers, p>>n, m>>n


François Grieu

Phil l'ancien
Le #570800
Francois Grieu
Phil l'ancien



Disons que j'ai une liste de nombres entiers (*), que
j'ai transmise par différents moyens, éventuellement
en plusieurs fois, à des destinataires.
...
Dans cette application, il n'y a pas de besoin
sur la confidentialité, l'authenticité, la falsification, etc.
Juste un risque de mauvaise transmission
ou d'erreur de prise en compte des transmissions.




Ce n'est pas l'acception courante de 'intégrité' dans ce
forum de cryptographie, qui s'intéresse aux adversaires qui
modifient sciemment les données; d'où mon précédent message.


C'est vrai. Désolé d'être un peu HS.

Exemples d'algos possibles :
...


Une point qui a son importance: l'ordre des entiers est-il
significatif ? Dans les techniques citées en exemple, la
permutation d'éléments de la liste n'est pas détectée.
C'est peut-être une faiblesse non voulue.
...


Dans mon application, l'ordre n'est pas significatif.
(l'utilisation est de vérifier la non appartenance
d'un nombre à la liste)


Connaissez-vous un algo efficace de ce type ?


Pour pouvoir garantir rigoureusement la fiabilité de la
détection d'erreur accidentelle sans connaitre du tout
le mode de de transmission, la solution radicale (et
habituelle) est d'exprimer la liste d'entiers de manière
bien définie en une suite d'octet (ou de bits), et en
général on choisi la forme sous laquelle ces informations
sont échangées; puis d'utiliser un hash cryptographique
appliqué à cette suite.


Oui, c'est exactement ça.
On projette un hash (cryptographique ou non)
pour la transmission des mises à jour.

Mais ça laisse la question de l'integrité (au sens
de la détection d'erreur, sans adversaire) des
données après prise en compte dans le système
d'information du destinataire.


En théorie, la même technique ne fonctionne pas avec un CRC,
car on ne peut exclure que le canal de transmission ait une
forte propension à ne faire que des erreurs qui n'altèrent
par ce CRC (exemple classique: si le canal de transmission
corrige ses erreurs avec le même polynôme).


Oui, d'accord avec vous, il faut un autre contrôle que
celui de la transmission. Un contrôle autant que possible
"orthogonal", si on peut dire.


Si, comme dans votre cas, on ingore la méthode de
transmission et de stockage, on défini précisément une
transformation de la liste de nombres en une suite d'octets
(ou de bits); il y a au moins un standard, ASN-1.
Ou encore, on prend une méthode ad-hoc simple, exemple:
si on sait que chaque entier est dans l'intervalle [0..2^32-1],
on peut dire que chaque entier est représenté par 32 bits
codant sa valeur en base 2, poids fort en tête; noter que
cette convention simplifie le calcul du hash SHA-1, car pour
celui-ci on commence par regrouper les bits en entiers selon
la convention exactement inverse, de sorte que les deux
transcodages sucessifs deviennent superflus.



Les nombres de mon application sont inférieurs à 2^40 -1.

Si je vous comprend bien, on pourrait faire deux
contrôles par SHA-1 :
- un contrôle de transmission, dans l'ordre big-endian
- un contrôle de prise en compte, dans l'ordre little-endian

(ou l'inverse) c'est bien ça ?


Je ne connais pas d'autre technique standard de valeur de
contrôle de liste d'entiers. Toutefois il me semble que l'on
peut construire un algorithme simple, travaillant directement
sur les entiers, et à résistance démontrable aux erreurs
accidentelles: on choisi comme paramètres deux nombres
premiers distincts m et n, tels que 1/n est plus petit que
la probabilité d'erreur non détectée désirée .../


__________________________________________________
A partir de là, je suis perdu... pourtant je suis un ingénieur, purée !
bon, ok, pas de polytechnique ;-)


/...
; et l'on calcule

la valeur de contrôle v des entiers aj de la liste par
v := 0
pour chaque entier aj de la liste
v := (v * m + aj) % n
On peut je crois démontrer la résistance de ceci, dans un
modèle où l'on fixe des listes en erreurs, et où n et m
sont choisis indépendemment, au hasard; on en déduit que
ça marche en pratique si m et n sont choisis d'une manière
qui est sans rapport avec le canal de transmission.
Avec m = 37, n = 56512723, et 0<=aj<56512897,
v * m + aj < 2^31 ce qui permet un calcul assez facile
dans de nombreux languages. Noter qu'il est très facile
de provoquer une collision (les listes 1,0 et 0,37 sont
en collision), pour rendre celà moins probable il faut
augmenter m, mais du coup il faut réduire n si l'on à une
limitation pratique pour le produit m*n.

Si l'ordre de la liste doit ne pas être significatif,
on peut trier la liste avant calcul de la valeur de
contrôle, mais c'est un peu lourd.

Sans tri, et à niveau d'erreur démontrable dans le sens
ci-dessus, c'est peut-être possible avec quelque chose
dans le genre (je ne promet rien)
v := 0
pour chaque entier aj de la liste
v := (v + 1 + ((aj * m) % p)) % n
avec les paramètres m n p premiers, p>>n, m>>n



François Grieu



Francois Grieu
Le #570799
Le 1 avr, 03:00, "Phil l'ancien"
Dans mon application, l'ordre n'est pas significatif.
(l'utilisation est de vérifier la non appartenance
d'un nombre à la liste)


Voila une particularité pas courante en cryptographie.
Un hash cryptographique est sensible à l'ordre.
Un hash cryptographique sur et non sensible à l'ordre,
je ne sais faire qu'en triant puis en hashant.
Par contre on sais faire un code d'authentification
de message avec cette proriété (la différence entre
les deux, c'est que dans le second il y a une clé
inconnue de l'adversaire).

Connaissez-vous un algo efficace de ce type ?
Pour pouvoir garantir rigoureusement la fiabilité de la

détection d'erreur accidentelle sans connaitre du tout
le mode de de transmission, la solution radicale (et
habituelle) est d'exprimer la liste d'entiers de manière
bien définie en une suite d'octet (ou de bits), et en
général on choisi la forme sous laquelle ces informations
sont échangées; puis d'utiliser un hash cryptographique
appliqué à cette suite.


Oui, c'est exactement ça.
On projette un hash (cryptographique ou non)
pour la transmission des mises à jour.

Mais ça laisse la question de l'integrité (au sens
de la détection d'erreur, sans adversaire) des
données après prise en compte dans le système
d'information du destinataire.


Cea ressemble à la question de la mise à jour de la
"liste noire" dans les les terminaux de paiement.
Une méthode est de protéger chaque liste et mise à
jour cryptographiquement, et de faire que chaque liste
et mise à jour contienne une horodate, et chaque mise
à jour l'horodate de la liste (ou mise à jour) servant de
référence. Si une mise à jour n'a pas l'horodate
attendue, le terminal la rejette, et/ou re-télécharge
toute la liste, et/ou les mises à jour adéquates.
De la sorte, le contrôle d'intégrité (au sens crypto)
de ce qui est transmis suffit à prouver l'intégrité
de l'ensemble que maintient le terminal par rapport à
tout problème de transmission, intentionnel ou pas.
Le risque de dysfonctionnement du terminal est traité
localement par le terminal, qui est responsable de
de vérifier qu'un bit de sa mémoire n'a pas sauté, sans
qu'il soit utilisé une valeur de contrôle indépendante
de la plateforme pour la liste noire courante, autant
que je sache.

(..)
Il faut un autre contrôle que celui de la transmission
Un contrôle autant que possible "orthogonal", si on peut dire.


La question de l'orthogonalité se pose uniquement pour
des codes de contrôle non cryptographiques. Avec un hash
cryptographique sur, on peut exclure qu'un changement
ne change pas le hash, et donc il n'y a pas d'inconvénient
à ré-utiliser le même hash pour des contrôles sucessifs.

Si, comme dans votre cas, on ingore la méthode de
transmission et de stockage, on défini précisément une
transformation de la liste de nombres en une suite d'octets
(ou de bits); il y a au moins un standard, ASN-1.
Ou encore, on prend une méthode ad-hoc simple, exemple:
si on sait que chaque entier est dans l'intervalle [0..2^32-1],
on peut dire que chaque entier est représenté par 32 bits
codant sa valeur en base 2, poids fort en tête; noter que
cette convention simplifie le calcul du hash SHA-1, car pour
celui-ci on commence par regrouper les bits en entiers selon
la convention exactement inverse, de sorte que les deux
transcodages sucessifs deviennent superflus.


Les nombres de mon application sont inférieurs à 2^40-1.


L'optimisation que je disais n'est doc pas applicable.
Reste ASN-1, et les deux formats naturels: poids faible
en tête ou poids fort en tête. En crypto standardisée,
la tendance est au poids fort en tête, et si le hash est
SHA-1, celà s'impose presque.

Si je vous comprend bien, on pourrait faire deux
contrôles par SHA-1 :
- un contrôle de transmission, dans l'ordre big-endian
- un contrôle de prise en compte, dans l'ordre little-endian
(ou l'inverse) c'est bien ça ?


Tous les contrôles peuvent utiliser exactement le même hash
si il est cryptographiquement sur. Le dernier contrôle
effectué protège contre tout: altérations intentionelles
et accidentelles lors de la transmission et du stockage.

Je ne connais pas d'autre technique standard de valeur de
contrôle de liste d'entiers. Toutefois il me semble que l'on
peut construire un algorithme simple, travaillant directement
sur les entiers, et à résistance démontrable aux erreurs
accidentelles: on choisi comme paramètres deux nombres
premiers distincts m et n, tels que 1/n est plus petit que
la probabilité d'erreur non détectée désirée .../


A partir de là, je suis perdu... pourtant je suis un
ingénieur, purée ! bon, ok, pas de polytechnique ;-)


Pareil pour moi, en ce qui concerne la formation.

Bon je reformule: mon but est de construire une somme de contrôle
qui ne manipule les nombres qu'avec des opérateurs présents
dans la pluspart des plateformes, ce qui exclu en particulier
l'opérateur XOR par exemple, qui est très difficile à implementer
dans mon tableur habituel; et donc exclu SHA-1.
Mais je veux pouvoir donner un argument rigoureux que la somme de
contrôle résiste aux erreur non intentionelles.
Ma démarche, standard en crypto académique, est de construire une
famille de sommes de contrôles, et de démontrer que face à un
adversaire qui ingore quelle membre de la famille j'ai choisi,
la probabiltié qu'une altération (y compris intentionelle) soit
non détectée, est inférieure à un seuil.
Je dis que si j'ai une telle famille, il suffit que j'en prenne
un membre particulier au hasard, et/donc sans rapport avec le genre
d'erreur accidentelle que je vais rencontrer en pratique, pour être
"certain" de ma capacité de détection d'erreur: les erreurs non
intentionelles n'ont "aucne raison" de m'être plus défavorables que
des erreurs intentionelles.
La limite de cette démarche, c'est que la preuve de sécurité pour
la famille est administrée quand le paramètre est dans un ensemble
dont la taille tend vers l'infini, et que l'on doit utiliser des
paramètres finis; d'où la nécessité de choisir des paramètres avec
un certain doigté.

Relisez la suite, ça devrait être compréhensible.

l'on calcule la valeur de contrôle v des entiers aj de la
liste par
v := 0
pour chaque entier aj de la liste
v := (v * m + aj) % n
On peut je crois démontrer la résistance de ceci, dans un
modèle où l'on fixe des listes en erreurs, et où n et m
sont choisis indépendemment, au hasard; on en déduit que
ça marche en pratique si m et n sont choisis d'une manière
qui est sans rapport avec le canal de transmission.
Avec m = 37, n = 56512723, et 0<=aj<56512897,
v * m + aj < 2^31 ce qui permet un calcul assez facile
dans de nombreux languages. Noter qu'il est très facile
de provoquer une collision (les listes 1,0 et 0,37 sont
en collision), pour rendre celà moins probable il faut
augmenter m, mais du coup il faut réduire n si l'on à une
limitation pratique pour le produit m*n.

Si l'ordre de la liste doit ne pas être significatif,
on peut trier la liste avant calcul de la valeur de
contrôle, mais c'est un peu lourd.
Sans tri, et à niveau d'erreur démontrable dans le sens
ci-dessus, c'est peut-être possible avec quelque chose
dans le genre (je ne promet rien)
v := 0
pour chaque entier aj de la liste
v := (v + 1 + ((aj * m) % p)) % n
avec les paramètres m n p premiers, p>>n, m>>n



François Grieu



Phil l'ancien
Le #570798
Francois Grieu
Phil l'ancien

Dans mon application, l'ordre n'est pas significatif.




Connaissez-vous un algo efficace de ce type ?


Pour pouvoir garantir rigoureusement la fiabilité de la
détection d'erreur accidentelle sans connaitre du tout
le mode de de transmission, la solution radicale (et
habituelle) est d'exprimer la liste d'entiers de manière
bien définie en une suite d'octet (ou de bits), et en
général on choisi la forme sous laquelle ces informations
sont échangées; puis d'utiliser un hash cryptographique
appliqué à cette suite.


Oui, c'est exactement ça.
On projette un hash (cryptographique ou non)
pour la transmission des mises à jour.

Mais ça laisse la question de l'integrité (au sens
de la détection d'erreur, sans adversaire) des
données après prise en compte dans le système
d'information du destinataire.


Oui, c'est c'est exactement ça le besoin.
On sait déjà par ailleurs vérifier l'absence d'erreur
dans la transmission des mises à jour, et là je
cherche le moyen de vérifier l'absence d'erreur
après prise en compte (prise en compte cumulative
de plusieurs transmissions).



Ca ressemble à la question de la mise à jour de la
"liste noire" dans les les terminaux de paiement.


En effet, ça ressemble beaucoup.
Mon application est une liste noire de
numéros de série.


Je ne connais pas d'autre technique standard de valeur de
contrôle de liste d'entiers. Toutefois il me semble que l'on
peut construire un algorithme simple, travaillant directement
sur les entiers, et à résistance démontrable aux erreurs
accidentelles: on choisi comme paramètres deux nombres
premiers distincts m et n, tels que 1/n est plus petit que
la probabilité d'erreur non détectée désirée .../



Bon je reformule: mon but est de construire une somme de contrôle
qui ne manipule les nombres qu'avec des opérateurs présents
dans la pluspart des plateformes, ce qui exclu en particulier
l'opérateur XOR par exemple, qui est très difficile à implementer
dans mon tableur habituel; et donc exclu SHA-1.


Les plateformes utilisées dans mon appli savent
toutes faire le XOR, mais d'accord avec vous, autant
l'éviter puisqu'il faudrait faire des hypothèses sur
l'implémentation des entiers.


Mais je veux pouvoir donner un argument rigoureux que la
somme de contrôle résiste aux erreur non intentionelles.
Ma démarche, standard en crypto académique, est de construire une
famille de sommes de contrôles, et de démontrer que face à un
adversaire qui ingore quelle membre de la famille j'ai choisi,
la probabiltié qu'une altération (y compris intentionelle) soit
non détectée, est inférieure à un seuil.
Je dis que si j'ai une telle famille, il suffit que j'en prenne
un membre particulier au hasard, et/donc sans rapport avec le genre
d'erreur accidentelle que je vais rencontrer en pratique, pour être
"certain" de ma capacité de détection d'erreur: les erreurs non
intentionelles n'ont "aucne raison" de m'être plus défavorables que
des erreurs intentionelles.


D'accord avec votre démarche.


l'on calcule la valeur de contrôle v des entiers aj de la
liste par
v := 0
pour chaque entier aj de la liste
v := (v * m + aj) % n
On peut je crois démontrer la résistance de ceci, dans un
modèle où l'on fixe des listes en erreurs, et où n et m
sont choisis indépendemment, au hasard; on en déduit que
ça marche en pratique si m et n sont choisis d'une manière
qui est sans rapport avec le canal de transmission.
Avec m = 37, n = 56512723, et 0<=aj<56512897,
v * m + aj < 2^31 ce qui permet un calcul assez facile
dans de nombreux languages. Noter qu'il est très facile
de provoquer une collision (les listes 1,0 et 0,37 sont
en collision), pour rendre celà moins probable il faut
augmenter m, mais du coup il faut réduire n si l'on à une
limitation pratique pour le produit m*n.





L'algorithme me convient plutôt bien.
Dans votre exemple, n est très proche de
la borne supérieure des entiers aj.
Est-ce une nécessité ?

Pouvez-vous m'indiquer comment on
détermine la probabilité (le risque) qu'une
erreur accidentelle ne soit pas détectée ?


Si l'ordre de la liste doit ne pas être significatif,
on peut trier la liste avant calcul de la valeur de
contrôle, mais c'est un peu lourd.
Sans tri, et à niveau d'erreur démontrable dans le sens
ci-dessus, c'est peut-être possible avec quelque chose
dans le genre (je ne promet rien)
v := 0
pour chaque entier aj de la liste
v := (v + 1 + ((aj * m) % p)) % n
avec les paramètres m n p premiers, p>>n, m>>n





Ca m'intéresse aussi, ainsi on supprime la
nécessité de trier la liste.

Pouvez-vous m'indiquer une piste sur la
manière de calculer le niveau d'erreur
(probabilté d'une erreur accidentelle non détectée) ?


Phil l'ancien-



Francois Grieu
Le #570797
Dans l'article "Phil l'ancien"
On sait déjà par ailleurs vérifier l'absence d'erreur
dans la transmission des mises à jour, et là je
cherche le moyen de vérifier l'absence d'erreur
après prise en compte (prise en compte cumulative
de plusieurs transmissions).


En fait, un bête OU exclusif, ou une addition modulo 2^40,
c'est un compromis sensé entre efficacité et complexité
dès lors que la transmission de chaque morceau de liste
est faite avec contrôle cryptographique (qui est "orthogonal"
à cette vérification); c'est insensible à l'ordre (mais pas
à la présence de numéros en double), et la probabilité de
ne pas détecter une erreur aléatoire est de 1 sur un million
de million, avec des hypothèses raisonables sur le caractère
aléatoire de chaque élément de liste transmis.


Francois Grieu
l'on calcule la valeur de contrôle v des entiers aj de la
liste par
v := 0
pour chaque entier aj de la liste
v := (v * m + aj) % n
On peut je crois démontrer la résistance de ceci, dans un
modèle où l'on fixe des listes en erreurs, et où n et m
sont choisis indépendemment, au hasard; on en déduit que
ça marche en pratique si m et n sont choisis d'une manière
qui est sans rapport avec le canal de transmission.
Avec m = 37, n = 56512723, et 0<=aj<56512897,
v * m + aj < 2^31 ce qui permet un calcul assez facile
dans de nombreux languages. Noter qu'il est très facile
de provoquer une collision (les listes 1,0 et 0,37 sont
en collision), pour rendre celà moins probable il faut
augmenter m, mais du coup il faut réduire n si l'on à une
limitation pratique pour le produit m*n.


L'algorithme me convient plutôt bien.
Dans votre exemple, n est très proche de
la borne supérieure des entiers aj.
Est-ce une nécessité ?


Non; j'ai choisi les paramètres comme cela, de manière à ce
que si la borne supérieure des aj est plus grande que n, il
soit facile de faire le calcul sous la forme
v := (v * m + (aj % n)) % n

Pouvez-vous m'indiquer comment on détermine la probabilité
(le risque) qu'une erreur accidentelle ne soit pas détectée ?


Ca a été zappé lors d'une citation, je le suggérais dans
on choisi comme paramètres deux nombres premiers
distincts m et n, tels que 1/n est plus petit que
la probabilité d'erreur non détectée désirée;





La probabilité d'erreur non détectée est 1/n pour des erreurs
aléatoires massives, et (pour des paramètres m et n bien choisis)
face aux erreurs aléatoires rencontrées en pratique, genre
erreurs de quelques bits. Il est certain que toute erreur
affectant un seul aj et changeant aj%n est détectée, donc pour
des aj en binaire toute erreur n'excédant pas log2(n) bits
consécutifs et affectant un seul aj est détectée.

Il est recommandable que PGCD(m,n) = 1 (condition toujours
remplie pour m et n premiers distincts), que |m%n| ne
soit pas trop petit, et que ni cette quantité ni n n'aient
une expression trop régulière dans le/les systèmes de
numération utilisés.

Je suis désolé de ne pas trouver de référence pour tout cela,
dans ce cas on dit: cela fait partie du folklore. En tout cas
je ne l'ai pas inventé.


Si l'ordre de la liste doit ne pas être significatif,
on peut trier la liste avant calcul de la valeur de
contrôle, mais c'est un peu lourd.
Sans tri, et à niveau d'erreur démontrable dans le sens
ci-dessus, c'est peut-être possible avec quelque chose
dans le genre (je ne promet rien)
v := 0
pour chaque entier aj de la liste
v := (v + 1 + ((aj * m) % p)) % n
avec les paramètres m n p premiers, p>>n, m>>n


Ca m'intéresse aussi, ainsi on supprime la
nécessité de trier la liste.


Euh, à la réflexion, ce truc hativement bricolé n'est pas
à sécurité démontrable, et même est démontrablement faible:
la liste 1,4 et la liste 2,3 ont une très fâcheuse tendance
à être en collision, c'est à peine mieux qu'une checksum.

Deuxème tentative
v := 0
pour chaque entier aj de la liste
v := (v + (aj*(aj+m)) % p ) % n
avec m n p premiers distincts, p > m >> n

Attention: je n'ai pas de preuve de sécurité, juste pas de
contre exemple (et une illustration, ci dessus, que je me
trompe souvent dans mes réflexions hâtives).
Cette méthode est insensible à l'ordre, mais est sensible
à la présence d'un nombre en plusieurs exemplaires
(contre les doublons, il faut une autre méthode, et il y
a un compromis mémoire/efficacité).
Aussi, si les résultats intermédiaires doivent être
inférieurs à 2^31, n va être limité, genre 1000.
On peut partiellement compenser cet inconvénient en faisant
plusieurs sommes avec des paramètres différents.


Francois Grieu




Phil l'ancien
Le #570796
Francois Grieu


En fait, un bête OU exclusif, ou une addition modulo 2^40,
c'est un compromis sensé entre efficacité et complexité
dès lors que la transmission de chaque morceau de liste
est faite avec contrôle cryptographique (qui est "orthogonal"
à cette vérification); c'est insensible à l'ordre (mais pas
à la présence de numéros en double), et la probabilité de
ne pas détecter une erreur aléatoire est de 1 sur un million
de million, avec des hypothèses raisonables sur le caractère
aléatoire de chaque élément de liste transmis.


L'addition modulo 2^40 me conviendrait encore mieux
que la valeur de contrôle à base de 2 premiers.
Beaucoup plus simple, et si le risque est effectivement
de 1/2^40, c'est tout à fait correct.

J'aurai besoin de pouvoir indiquer le nom de la méthode,
et de documenter un minimum le risque.
Pouvez-vous m'indiquer une référence, un article de
wikipedia, ou quelque chose de ce genre ?


Phil l'ancien-

Publicité
Poster une réponse
Anonyme