Intel Secure Key RNG ¿Seguro?

[AlbertoBSD]

Un poco de Background antes de empezar.

¿Que es un RNG?

Segun Wikipedia[1]: Random Number Generation, es el proceso de crear una secuencia de numeros o simbolos que no deben de ser predecibles.

Importancia de numeros Aleatorios

Para entender la importancia de los numeros aleatorios tenemos que preguntarnos ¿Donde utilizamos numeros Aleatorios?

Segun Schneier B. (2000)  Yarrow-160: Notes on the Design and Analysis of the Yarrow Cryptographic Pseudorandom Number Generator recuperado de [2]

Los numeros Aleatorios en Criptografia son usados por

• Sesiones y llaves de mensajes para algoritmos de cifrado simetrico como tripe-Des Blowsh
• Como semillas para rutinas que generan valores matematicos como numeros primos muy grandes para RSA
• Saltos de password para frustrar ataques por fuerza bruta fuera de linea
• Vectores de Inicializacion (IV) para bloques de algoritmos de cidrado (AES CBC, ECB etc)
• Valores Aleatorios para Firmas Digitales de Cifrado como  DSA
• Desafios Aleatorios en protocolos de Autenticacion como Kerberos
• "Nonces" para protocolos y garantizar que cada ejecucion es unicia SSL

Me tome la molestia de traducir y agregar toda la lista para ejemplificar que el uso de numeros aleatorios es muy basto y mas comun de lo que piensan, cada que entran a una pagina web con SSL activado se generan numeros aleatorios.

Ahora ya con este Background sobre los RNG y el uso de numeros aleatorios en cryptogradia es posible  entrar en el Tema del Post

¿Que es el "Intel Secure Key RNG"?

Si bien por el nombre podriamos pensar que alguna especie de Llave USB o alguna pienza sofisticada de Hardware, pues estamos en un error!!
El mencionado Intel Secure Key RNG no es nada mas que una Instruccion nueva para procesadores modernos de Intel la cual nos devuelve valores aleatorios Generados directamente por el procesador [3]

Esto es Genial ya que en teoria le quita la Carga al Sistema Operativo de Generar Numeros Aleatorios utilizando algoritmos pesados
¿O no?

Pues bien dada la desconfianza que existe hacia cualquier implentacion del tipo privado, debido a debilidades y/o backdoors documentados. Los sistemas operativos modernos no toman estos "sources" de numeros aleatorios para servirlos directamente a las aplicaciones que soliciten numeros aleatorios, sino que los pasan atraves de algun algoritmo adicional y finalmente sirven sus propios numeros generados.

Esto lo hacen con el objetivo de elimiar cualquier rastro de backdoor que pueda existir.

La instruccion rdrand es usada por sistemas como Linux[4] y FreeBSD[5]  entre otros para  sus plataformas de Intel. Y como se menciono no la usan como valor directo, si no como uno de tantos origenes de Entropia para sus algoritmos de /dev/random

Personalmente he trabajado con el Kernel de FreeBSD y he visto en el codigo[6] el uso de la instruccion rdrand.

Entonces que formas tenemos para analizar si la salida directa de rdrand es segura.

Repasemos las caracteristicas que debe tener un RNG, segun [3]

• Cada valor nuevo debe de ser estadisticamente independiente del anterior
• La distribucion de todos los numeros generados debe de ser Uniforme
• La secuencia debe de ser impredecible

Entonces para la comparacion usare varias muestras de 1MB del Disposivo random estandar del sistema, Para este ejemplo /dev/random de FreeBSD 11.1 RELEASE contra varias muestras de 1MB de la salida devuelta directamente por rdrand.

Para hacer esto lo mas amigable posible desarrolle un modulo para el kernel de FreeBSD [7] que al igual que /dev/random, nos genera un device /dev/rdrand que nos devuelve un stream de numeros aleartorios pero en esta ocacion tomados directamente de la instruccion rdrand para procesadores Ivy Bridge.

Codigo para generar un archivo de muestra:

Código [Seleccionar] Expandir


dd if=/dev/random of=~/random.test count=1 bs=1M
dd if=/dev/rdrand of=~/rdrand.test count=1 bs=1M


Asi mismo desarrolle un programa que lee un archivo y cuenta el numero de veces que aparece cada valor en dicho archivo:


Salida del primer archivo

Código [Seleccionar] Expandir

Abriendo ./random.test
Valor 0: 4161
Valor 1: 4307
Valor 2: 3964
Valor 3: 4124
Valor 4: 4076
Valor 5: 4032
Valor 6: 4031
Valor 7: 4152
Valor 8: 4146
Valor 9: 4078
Valor 10: 4155
Valor 11: 4121
Valor 12: 4144
Valor 13: 4117
Valor 14: 4180
Valor 15: 3984
Valor 16: 4113
Valor 17: 4188
Valor 18: 4069
Valor 19: 4127
Valor 20: 3980
Valor 21: 4019
Valor 22: 3959
Valor 23: 4067
Valor 24: 4054
Valor 25: 4124
Valor 26: 4123
Valor 27: 4070
Valor 28: 4151
Valor 29: 4178
Valor 30: 4115
Valor 31: 4117
Valor 32: 4119
Valor 33: 4090
Valor 34: 4120
Valor 35: 4126
Valor 36: 4053
Valor 37: 4055
Valor 38: 4084
Valor 39: 4048
Valor 40: 4137
Valor 41: 4125
Valor 42: 4029
Valor 43: 4060
Valor 44: 4077
Valor 45: 4128
Valor 46: 4205
Valor 47: 3959
Valor 48: 4082
Valor 49: 4019
Valor 50: 4034
Valor 51: 4107
Valor 52: 4125
Valor 53: 4112
Valor 54: 4050
Valor 55: 4011
Valor 56: 4087
Valor 57: 4071
Valor 58: 4039
Valor 59: 4095
Valor 60: 4093
Valor 61: 4088
Valor 62: 4091
Valor 63: 4006
Valor 64: 4081
Valor 65: 4047
Valor 66: 4102
Valor 67: 4138
Valor 68: 4106
Valor 69: 4019
Valor 70: 4167
Valor 71: 4118
Valor 72: 4145
Valor 73: 4216
Valor 74: 4129
Valor 75: 4210
Valor 76: 4188
Valor 77: 4079
Valor 78: 4130
Valor 79: 4156
Valor 80: 4129
Valor 81: 4075
Valor 82: 4069
Valor 83: 4097
Valor 84: 4113
Valor 85: 4034
Valor 86: 4107
Valor 87: 3944
Valor 88: 4084
Valor 89: 4310
Valor 90: 4082
Valor 91: 4075
Valor 92: 4110
Valor 93: 4113
Valor 94: 4063
Valor 95: 4133
Valor 96: 4207
Valor 97: 4031
Valor 98: 4166
Valor 99: 4009
Valor 100: 4249
Valor 101: 4076
Valor 102: 4155
Valor 103: 4051
Valor 104: 4052
Valor 105: 4115
Valor 106: 4157
Valor 107: 4013
Valor 108: 4093
Valor 109: 4076
Valor 110: 4126
Valor 111: 4156
Valor 112: 4099
Valor 113: 4079
Valor 114: 4049
Valor 115: 4125
Valor 116: 4018
Valor 117: 3990
Valor 118: 4014
Valor 119: 4114
Valor 120: 4058
Valor 121: 4086
Valor 122: 4016
Valor 123: 4034
Valor 124: 3991
Valor 125: 4044
Valor 126: 4224
Valor 127: 4047
Valor 128: 4189
Valor 129: 4160
Valor 130: 4056
Valor 131: 4073
Valor 132: 4009
Valor 133: 4154
Valor 134: 4163
Valor 135: 4130
Valor 136: 4108
Valor 137: 4226
Valor 138: 4099
Valor 139: 4198
Valor 140: 4004
Valor 141: 4037
Valor 142: 4139
Valor 143: 4129
Valor 144: 4085
Valor 145: 4211
Valor 146: 4036
Valor 147: 4010
Valor 148: 4136
Valor 149: 4167
Valor 150: 4135
Valor 151: 4100
Valor 152: 4061
Valor 153: 4115
Valor 154: 4022
Valor 155: 4074
Valor 156: 4164
Valor 157: 3978
Valor 158: 3999
Valor 159: 4041
Valor 160: 4094
Valor 161: 4003
Valor 162: 4008
Valor 163: 4063
Valor 164: 4200
Valor 165: 4202
Valor 166: 4192
Valor 167: 3978
Valor 168: 4120
Valor 169: 4133
Valor 170: 4204
Valor 171: 4176
Valor 172: 4100
Valor 173: 4092
Valor 174: 4109
Valor 175: 4071
Valor 176: 4091
Valor 177: 4067
Valor 178: 4044
Valor 179: 4070
Valor 180: 4024
Valor 181: 4012
Valor 182: 4130
Valor 183: 4062
Valor 184: 4096
Valor 185: 4092
Valor 186: 4110
Valor 187: 4031
Valor 188: 3931
Valor 189: 4065
Valor 190: 4156
Valor 191: 4167
Valor 192: 4033
Valor 193: 4176
Valor 194: 4000
Valor 195: 4174
Valor 196: 4054
Valor 197: 4126
Valor 198: 4121
Valor 199: 4089
Valor 200: 4154
Valor 201: 4192
Valor 202: 4087
Valor 203: 4164
Valor 204: 4176
Valor 205: 4134
Valor 206: 4082
Valor 207: 4103
Valor 208: 4234
Valor 209: 4022
Valor 210: 3978
Valor 211: 4188
Valor 212: 4104
Valor 213: 4168
Valor 214: 4005
Valor 215: 4065
Valor 216: 4118
Valor 217: 4102
Valor 218: 4108
Valor 219: 4077
Valor 220: 4094
Valor 221: 3951
Valor 222: 4078
Valor 223: 4005
Valor 224: 4012
Valor 225: 4131
Valor 226: 4190
Valor 227: 4058
Valor 228: 4036
Valor 229: 4111
Valor 230: 4137
Valor 231: 4000
Valor 232: 4175
Valor 233: 4164
Valor 234: 4253
Valor 235: 4067
Valor 236: 4081
Valor 237: 4037
Valor 238: 4116
Valor 239: 4155
Valor 240: 4137
Valor 241: 4025
Valor 242: 4052
Valor 243: 4140
Valor 244: 4132
Valor 245: 4115
Valor 246: 4063
Valor 247: 3924
Valor 248: 4174
Valor 249: 4098
Valor 250: 4115
Valor 251: 4105
Valor 252: 4083
Valor 253: 4138
Valor 254: 4152
Valor 255: 4098


Salida del segundo archivo

Código [Seleccionar] Expandir

Abriendo ./rdrand.test
Valor 0: 4043
Valor 1: 4055
Valor 2: 4191
Valor 3: 4058
Valor 4: 4125
Valor 5: 4087
Valor 6: 4090
Valor 7: 4150
Valor 8: 4007
Valor 9: 4139
Valor 10: 4027
Valor 11: 4054
Valor 12: 4059
Valor 13: 4167
Valor 14: 4024
Valor 15: 4115
Valor 16: 4045
Valor 17: 4135
Valor 18: 4007
Valor 19: 3980
Valor 20: 4169
Valor 21: 4131
Valor 22: 3997
Valor 23: 4051
Valor 24: 4223
Valor 25: 4110
Valor 26: 4185
Valor 27: 4109
Valor 28: 4052
Valor 29: 4093
Valor 30: 4108
Valor 31: 4163
Valor 32: 4119
Valor 33: 4129
Valor 34: 4180
Valor 35: 4061
Valor 36: 4010
Valor 37: 4082
Valor 38: 4104
Valor 39: 4116
Valor 40: 4080
Valor 41: 4191
Valor 42: 4061
Valor 43: 4103
Valor 44: 4249
Valor 45: 4165
Valor 46: 4043
Valor 47: 4187
Valor 48: 4121
Valor 49: 4141
Valor 50: 4113
Valor 51: 4093
Valor 52: 4177
Valor 53: 3970
Valor 54: 4195
Valor 55: 4156
Valor 56: 4065
Valor 57: 4171
Valor 58: 4113
Valor 59: 4041
Valor 60: 4128
Valor 61: 4189
Valor 62: 4067
Valor 63: 4102
Valor 64: 4063
Valor 65: 4143
Valor 66: 4041
Valor 67: 4029
Valor 68: 4085
Valor 69: 4074
Valor 70: 4053
Valor 71: 4160
Valor 72: 4130
Valor 73: 4179
Valor 74: 4154
Valor 75: 4060
Valor 76: 4073
Valor 77: 4086
Valor 78: 4137
Valor 79: 4107
Valor 80: 4053
Valor 81: 4172
Valor 82: 4120
Valor 83: 4072
Valor 84: 3953
Valor 85: 4116
Valor 86: 4042
Valor 87: 4218
Valor 88: 4082
Valor 89: 3955
Valor 90: 4034
Valor 91: 4055
Valor 92: 4120
Valor 93: 4102
Valor 94: 3953
Valor 95: 4098
Valor 96: 4004
Valor 97: 3993
Valor 98: 4163
Valor 99: 3977
Valor 100: 4118
Valor 101: 4233
Valor 102: 4081
Valor 103: 4158
Valor 104: 4067
Valor 105: 4046
Valor 106: 4099
Valor 107: 4102
Valor 108: 4096
Valor 109: 4117
Valor 110: 4046
Valor 111: 4060
Valor 112: 4114
Valor 113: 4015
Valor 114: 4090
Valor 115: 4040
Valor 116: 4160
Valor 117: 4126
Valor 118: 4119
Valor 119: 4129
Valor 120: 4075
Valor 121: 4026
Valor 122: 4000
Valor 123: 4088
Valor 124: 4144
Valor 125: 4182
Valor 126: 4119
Valor 127: 4076
Valor 128: 4068
Valor 129: 4142
Valor 130: 4042
Valor 131: 4038
Valor 132: 4110
Valor 133: 4125
Valor 134: 3985
Valor 135: 4216
Valor 136: 4018
Valor 137: 4113
Valor 138: 4046
Valor 139: 4149
Valor 140: 4063
Valor 141: 4050
Valor 142: 4132
Valor 143: 4108
Valor 144: 4036
Valor 145: 4028
Valor 146: 4153
Valor 147: 4179
Valor 148: 4139
Valor 149: 4072
Valor 150: 4168
Valor 151: 4009
Valor 152: 4095
Valor 153: 4115
Valor 154: 4041
Valor 155: 3954
Valor 156: 4092
Valor 157: 4093
Valor 158: 4035
Valor 159: 4096
Valor 160: 4033
Valor 161: 4133
Valor 162: 3989
Valor 163: 4203
Valor 164: 4048
Valor 165: 4152
Valor 166: 4103
Valor 167: 4195
Valor 168: 4105
Valor 169: 4082
Valor 170: 4046
Valor 171: 4018
Valor 172: 4267
Valor 173: 4201
Valor 174: 4209
Valor 175: 4100
Valor 176: 4009
Valor 177: 3983
Valor 178: 4135
Valor 179: 4168
Valor 180: 4068
Valor 181: 4044
Valor 182: 4013
Valor 183: 3994
Valor 184: 4071
Valor 185: 4062
Valor 186: 4152
Valor 187: 4044
Valor 188: 4078
Valor 189: 4141
Valor 190: 4033
Valor 191: 4133
Valor 192: 4064
Valor 193: 4158
Valor 194: 3962
Valor 195: 4145
Valor 196: 4119
Valor 197: 4040
Valor 198: 3981
Valor 199: 4173
Valor 200: 4025
Valor 201: 4090
Valor 202: 4067
Valor 203: 4049
Valor 204: 4106
Valor 205: 4232
Valor 206: 3987
Valor 207: 4053
Valor 208: 4121
Valor 209: 4177
Valor 210: 4214
Valor 211: 4053
Valor 212: 4095
Valor 213: 4127
Valor 214: 4082
Valor 215: 4109
Valor 216: 4107
Valor 217: 4181
Valor 218: 4224
Valor 219: 4142
Valor 220: 4112
Valor 221: 4165
Valor 222: 4121
Valor 223: 4088
Valor 224: 4073
Valor 225: 3984
Valor 226: 4112
Valor 227: 4054
Valor 228: 4151
Valor 229: 4120
Valor 230: 4040
Valor 231: 4129
Valor 232: 4099
Valor 233: 4085
Valor 234: 4078
Valor 235: 4149
Valor 236: 4101
Valor 237: 3985
Valor 238: 3999
Valor 239: 4085
Valor 240: 4138
Valor 241: 4300
Valor 242: 4078
Valor 243: 4265
Valor 244: 4194
Valor 245: 4027
Valor 246: 4130
Valor 247: 4225
Valor 248: 4111
Valor 249: 4102
Valor 250: 4046
Valor 251: 4059
Valor 252: 3974
Valor 253: 4096
Valor 254: 4155
Valor 255: 4089


A simple vista parece que ambas salidas tienen una distribucion uniforme de los valores, con esto comprobamos la segunda propiedad de los RNG "La distribucion de todos los numeros generados debe de ser Uniforme"

Falta validar las otras 2 propiedades pero de momento es suficiente.

¿Entonces podemos decir que el Intel Secure Key RNG es Seguro?

No de momento con las pruebas hechas no hay manera de afirmar que sea seguro o inseguro.

Sin embargo las concluciones mencionadas en[10] comentan que la instroduccion de rdrand en los sistemas mejora y simplifica la generacion de numeros aleatorios ademas recomiendan usarlo junto con otros sources de entropia.



Referencias
[1] https://en.wikipedia.org/wiki/Random_number_generation
[2] https://www.schneier.com/academic/paperfiles/paper-yarrow.pdf
[3] https://software.intel.com/sites/default/files/m/d/4/1/d/8/441_Intel_R__DRNG_Software_Implementation_Guide_final_Aug7.pdf
[4] https://www.theregister.co.uk/2013/09/10/torvalds_on_rrrand_nsa_gchq/
[5] https://arstechnica.com/information-technology/2013/12/we-cannot-trust-intel-and-vias-chip-based-crypto-freebsd-developers-say/
[6] https://svnweb.freebsd.org/base/release/11.1.0/sys/dev/random/ivy.c?view=markup
[7] https://github.com/albertobsd/rdrand
[8] https://eprint.iacr.org/2014/504.pdf
[9] http://spectrum.ieee.org/computing/hardware/behind-intels-new-randomnumber-generator
[10] http://www.electronicdesign.com/learning-resources/understanding-intels-ivy-bridge-random-number-generator