Algorithmes de hashage

Version imprimable

Bonjour à tous,

Je viens poster ici pour recevoir des avis / critiques sur un algorithme de hashages que j'ai développer aujourd’hui.
Il est codé en php.
Vu que je n'y connait rien en algo, il se peut que je soit partit dans une direction qui ne correspond pas du tout à ce que j’aurais du faire. Merci dès lors de me le dire.

Si néanmoins mon algorithme tient la route un minimum, je suis bien entendu prêts à écouter vos remarques pour l'améliorer.

L'algoritme est en démo ici.

la fonction de hash :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
function pershash($str){
	$id_table = array();
	$operations;
	$base = 0;
	$flashs = array();
	$hash;
	$reallenght = strlen($str);	
 
	if(isset($str) &&$reallenght>0 && $str !=""){
 
		for($i=0 ; $i<$reallenght ; $i++ ){
			$id_table[] = ord($str[$i]);
		}
 
		for($i=$reallenght ; $i<19 ; $i++ ){
			$id_table[$i] = floor(($id_table[$i-1]*M_SQRTPI)/M_SQRT3)+4;
		}
 
		$j = 0;
		foreach($id_table as $id){
			if(is_int($j/3)){
				$base += $j-$id;
			}else if(is_int($j/2)){
				$base += $j+$id;
			}else{
				$base -= $j+$id;
			}
		$j++;
		}
 
		$operations = 10000 *(M_PI / M_E)+$base;
		$j = 0;
		$nbr_ids = floor(count($id_table)/19);
 
		foreach($id_table as $id){
			if(is_int($id/55)){
				$operations -= asinh (intval($id));
			}
			else if(is_int($id/27)){
				$operations *= sqrt((intval($id)*0.01)/ M_LOG10E);
			}
			else if(is_int($id/13)){
				$operations /= round(intval($id)/ M_LN10)+M_EULER;
			}
			else if(is_int($id/9)){
				$operations -= M_PI+intval($id);
				$operations += 951;
			}
			else if(is_int($id/7)){
				$operations *= M_LNPI;
				$operations -= 456;
			}
			else if(is_int($id/4)){
				$operations -= round(intval($id)-44.7,8);	
				$operations *= round(M_PI_2,5);	
			}
			else if(is_int($id/3)){
				$operations /= intval($id)+3.77;
			}
			else if(is_int($id/2)){
				$operations += atan2(intval($id),(intval($id)/2)-M_SQRTPI);
			}
			else{
				$operations -= sin(intval($id));
			}
 
			$totest = intval($j)/intval($nbr_ids);
			if(is_int($totest)){
				$operations -= $id;
				$flashs[] = $operations;
				$operations /= $operations -0.9;
			}
			$j++;
		}
		$flashs[] = $operations-$id;
 
		$interm_hash="";
		$j = 0;
		foreach($flashs as $flash){
			$flash = str_replace (".","" , $flash."");
			$flash = str_replace ("-","" , $flash."");
			if(is_int($j/2)){
				$flash -= $reallenght;
			}else{
				$flash -= $base;
 
			}
			$flash .= "";
			$flash_temp = "";
			$flash_temp2 = "";
			for($i=0 ; $i<16 ; $i++ ){
				if(isset($flash[$i])){
					if(is_int($i/2)){
						$flash_temp .= $flash[$i];
					}else{
						$flash_temp2 .= $flash[$i];
					}
				}
			}
			$flash_temp = intval($flash_temp);
			$flash_temp2 = intval($flash_temp2);
 
			if(is_int($j/3)){
				$interm_hash.=intval($flash_temp).intval($flash_temp2);		
			}else if(is_int($j/2)){
				$interm_hash.=intval($flash_temp2).intval($flash_temp);	
			}else{
				$interm_hash=intval($flash_temp).intval($flash_temp2).$interm_hash;	
			}
			$j++;
		}
 
		if(is_int($base/5)){
			$interm_hash=substr($interm_hash,102).substr($interm_hash,0, 102);
		}else if(is_int($base/3)){
			$interm_hash=substr($interm_hash,97).substr($interm_hash,0, 97);
		}else if(is_int($base/2)){
			$interm_hash=substr($interm_hash,37).substr($interm_hash,0, 37);
		}else{
			$interm_hash=substr($interm_hash, 3 ).substr($interm_hash, 0 , 2);
		}
 
		$hash = "";
		for($i = 0 ; $i < strlen(strval($interm_hash))-8 ; $i+=8){
			$hash .= dechex(intval($interm_hash[$i].$interm_hash[$i+1].$interm_hash[$i+2].$interm_hash[$i+3].$interm_hash[$i+4].$interm_hash[$i+5].$interm_hash[$i+6].$interm_hash[$i+7]));
		}
 
		return $hash;
	}else{
		return false;
	}
}

Si j'ai bien compris, ca ressemble a peu près à cela:

                      _____________________
                     |                     |
                     |                    \|/
input-->[Transform]--+-->[S-BOX]--+-->[Transform]-->hash
                           /|\    |
                            |_____|

avec une S-BOX à base d'opérations mathématiques/trigo.

Tout d'abord suite à des remarques j'ai fait quelques modifs. J'ai aussi changé le code pour améliorer les performances.

Le voici :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
function pershash($str){
	if(!isset($str)){
		return false;
	}else{
		$id_table = array();
		$flashs = array();
		$base = 0;
		$reallenght = strlen($str);	
		$operations;
		$hash;
 
		$j = 0;
		$i=0;
 
		while($i < $reallenght){
			$id_table[] = ord($str[$i]);
			$i++;
		}
		while($i < 19){
			$id_table[$i] = floor(($id_table[$i-1]*M_SQRTPI)/M_SQRT3)+4;
			$i++;
		}		
		foreach($id_table as $id){
			($j % 3 == 0) ? $base += $j-$id : (($j % 2 == 0) ? $base += $j+$id : $base -= $j+$id);
		$j++;
		}
 
		$operations = 10000 *(M_PI / M_E)+$base;
		$nbr_ids = floor(count($id_table)/19);
 
		$j = 0;
		foreach($id_table as $id){
			switch (0) {
				case $id % 55:
					$operations -= asinh (intval($id));
					break;	
				case $id % 27:
					$operations *= sqrt((intval($id)*0.01)/ M_LOG10E);
					break;	
				case $id % 13:
					$operations /= round(intval($id)/ M_LN10)+M_EULER;
					break;	
				case $id % 9:
					$operations -= M_PI+intval($id);
					$operations += 951;
					break;	
				case $id % 7:
					$operations *= M_LNPI;
					$operations -= 456;
					break;	
				case $id % 4:
					$operations -= round(intval($id)-44.7,8);	
					$operations *= round(M_PI_2,5);	
					break;	
				case $id % 3:
					$operations /= intval($id)+3.77;
					break;	
				case $id % 2:
					$operations += atan2(intval($id),(intval($id)/2)-M_SQRTPI);
					break;					
				default:
					$operations -= sin(intval($id));
					break;
			}
 
			if($j % $nbr_ids == 0){
				$operations -= $id;
				$flashs[] = $operations;
				$operations /= $operations -0.9;
			}			
			$j++;
		}
		$flashs[] = $operations-$id;
 
		$interm_hash='';
		$j = 0;
		foreach($flashs as $flash){
			$flash = str_replace ('.','' , strval($flash));
			$flash = str_replace ('-','' , $flash);
 
			$flash = strval($flash -= ($j % 2 == 0) ? $reallenght : $base);
			$flash_temp = $flash_temp2 = $hash ='';
 
			$i=0;
			while($i < 16){
				(!isset($flash[$i])) ? : (($i % 2 == 0) ? $flash_temp .= $flash[$i] : $flash_temp2 .= $flash[$i]);
				$i++;
			}
			$interm_hash = ($j % 3 == 0) ? $interm_hash.$flash_temp.$flash_temp2 : (($j % 2 == 0) ? $interm_hash.$flash_temp2.$flash_temp : $flash_temp.$flash_temp2.$interm_hash);
			$j++;
		}		
		$interm_hash =($base % 5 == 0) ? substr($interm_hash,102).substr($interm_hash,0, 102) : (($base % 3 == 0) ? substr($interm_hash,97).substr($interm_hash,0, 97) : (($base % 2 == 0) ? substr($interm_hash,37).substr($interm_hash,0, 37) : substr($interm_hash, 3 ).substr($interm_hash, 0 , 2)));
 
		$max = strlen(strval($interm_hash));
		$max -= $max%8;
 
		$i=0;
		while($i < $max){
			$hash .= dechex(intval($interm_hash[$i].$interm_hash[$i+1].$interm_hash[$i+2].$interm_hash[$i+3].$interm_hash[$i+4].$interm_hash[$i+5].$interm_hash[$i+6].$interm_hash[$i+7]));
			$i+=8;
		}		
		return $hash;
	}
}

Ensuite pour répondre à pseudocode :
Vu que je n'y connait rien en algo, tu me parle un peu chinois la.
Mais après avoir tenté de comprendre ton schéma, je pense effectivement que ton schéma résume bien l'algo.

Juste que le mien est linéaire et ne fait donc pas de retour en arrière vers la S-box, ni de saut en avant. Il se contente de changer de s-box suivant l'input.

Du coup quelque choses comme ça ? mais je me trompe peut être.

Code:

1
2
3
4
5
6
7
8
 
                      -->[S-BOX]--
                     |            |
                     |            |
input-->[Transform]--+-->[S-BOX]--+-->[Transform]-->hash
                     |            |
                     |            |
                      -->[S-BOX]--

20/10/2011, 12h36
pseudocode
Citation:

Envoyé par Arcade007

Juste que le mien est linéaire et ne fait donc pas de retour en arrière vers la S-box, ni de saut en avant. Il se contente de changer de s-box suivant l'input.

Il y a un retour arrière au sens où tes opérations math/trigo sont effectuées en cascade, modifiant a chaque fois le résultat précédent.
```
$operations = init
foreach( element of input ){
  $operations =  sbox(operation, element)
}
```
ce qui est différent d'une simple opération linéaire
```
$operations =  sbox(init,input)
```
20/10/2011, 14h04
Arcade007

Ah oui, vu comme ça tu a raison effectivement.

Sinon je suis preneur de conseils pour améliorer les performances de la fonction.
20/10/2011, 14h49
pseudocode

Citation:

Envoyé par Arcade007

Ah oui, vu comme ça tu a raison effectivement.

Sinon je suis preneur de conseils pour améliorer les performances de la fonction.

Si tu parles de performance CPU, généralement on pré-calcule la S-BOX sous forme de table 2D.

Si tu parles de performance cryptographique (dispersion, avalanche), je n'en sais trop rien. :aie:
31/10/2011, 12h50
Jimmy_

Bonjour,

Les opérations de bases sont souvent des opérations binaires. Elles seront les plus rapide : comme des xor, ou des additions. Utiliser des fonctions trigo sans table pré-calculée rend ton algorithme trop lent.

Sinon je pense qu'il faut ajouter une S-Box fixe, car l'utilisation de la trigo doit très probablement induire des faiblesses pour certaines valeurs en entrée. Le rôle de ta S-Box fixe est de supprimer ces faiblesses. Mais bon tu n'as pas choisis ces fonctions par hasard, il doit bien y avoir un peu de théorie là derrière , non ?

Bon courage,