agosto 14, 2005

Mejorando la aleatoriedad en WanCatan 3.4.0beta

WanCatan es un juego multijugador que un amigo me pasó hace bastante tiempo, y al que asiduamente jugamos. Implementa todas las modalidades del juego de mesa Colonos de Catan y la mayoria de sus mejores expansiones.

Tras muchas partidas jugadas siempre teniamos la misma queja, los dados no se comportaban con demasiada realidad, había partidas en las que se repetian mucho ciertos numeros y esto minaba el juego.

Bien, decidido a echar un vistazo en las entrañas y armado con 2 excelentes programas (IDA y Ollydbg) he modificado la función de tirada de dados para intentar mejorar los resultados de los mismo.
A pesar de que la solución aportada no es aleatoriamente perfecta y es mejorable mediante otras tecnicas he usado este ejercicio a modo de aprendizaje.

Vamos allá:

1) Nuestra intención es encontrar el codigo que se encarga de la aleatoriedad de los dados:

Primero cargamos el .exe en el IDA y buscamos la referencia a la pulsación del boton de tirada de dados. Usando la función "find" encontramos la cadena que tiene todas las papeletas.

CODE:004741E4 00000010 C btThrowDiceClick


Observando el desensamblado vemos que antes de la cadena se encuentra una dirección de memoria que apunta dentro del programa:
CODE:004741DF dd offset loc_475498
CODE:004741E3 db 10h ;
CODE:004741E4 aBtthrowdicecli db 'btThrowDiceClick'
CODE:004741F4 db 15h ;
CODE:004741F5 db 0 ;

Siguiendo la posición de memoria (475498) a la que apunta el registro y un par de llamadas acabamos en la zona donde se "tiran" los dados:


CODE:00475204 ObtieneNumeroDados: ; CODE XREF: sub_475184+C3
CODE:00475204 mov eax, 6
CODE:00475209 call XXX_Random
CODE:0047520E mov ebx, eax
CODE:00475210 inc ebx
CODE:00475211 mov eax, 6
CODE:00475216 call XXX_Random
CODE:0047521B mov esi, eax
CODE:0047521D inc esi
CODE:0047521E mov eax, 6
CODE:00475223 call XXX_Random
CODE:00475228 inc eax
CODE:00475229 mov [ebp+var_C], eax
CODE:0047522C lea eax, [esi+ebx]
CODE:0047522F cmp eax, 7
CODE:00475232 jnz short loc_475249
CODE:00475234 mov eax, ds:off_4A9C90
CODE:00475239 cmp byte ptr [eax+37h], 0
CODE:0047523D jz short loc_475249
CODE:0047523F mov eax, ds:off_4A9EE8
CODE:00475244 cmp dword ptr [eax], 3
CODE:00475247 jle short ObtieneNumeroDados



CODE:00402BFC ; ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦ S U B R O U T I N E ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦
CODE:00402BFC
CODE:00402BFC
CODE:00402BFC XXX_Random proc near ; CODE XREF: sub_465420+B4p
CODE:00402BFC ; sub_475184+85p ...
CODE:00402BFC imul edx, ds:dword_4AA044, 8088405h
CODE:00402C06 inc edx
CODE:00402C07 mov ds:dword_4AA044, edx
CODE:00402C0D mul edx
CODE:00402C0F mov eax, edx
CODE:00402C11 retn
CODE:00402C11 XXX_Random endp


Es de especial interés la rutina anterior renombrada a "XXX_Random" (que recibe en EAX el limite a devolver), y que como observamos realiza los siguientes pasos:

  • Multiplica el resultado de la posicion de memoria 4AA044 por 8088405h y lo guarda en edx.
  • Incrementa EDX

  • Guarda EDX en la posicion de memoria 4AA044

  • Multiplica EDX * EAX colocando el resultado en EAX y la parte superior del numero en EDX

  • Mueve el resto (EDX) a EAX siendo este el resultado

Vemos que es claramente dependiente del registro de inicialización (4AA044)

2) Vamos a buscar donde anda la inicialización de ese registro, colocamos un breakpoint hw en escritura en esa posición de memoria e iniciamos el programa desde el principio para ver donde se realiza.

CODE:004029EC ; ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦ S U B R O U T I N E ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦
CODE:004029EC
CODE:004029EC ; Attributes: bp-based frame
CODE:004029EC
CODE:004029EC XXX_InicializaSemilla proc near ; CODE XREF: sub_4A5DFC+1Ap
CODE:004029EC
CODE:004029EC SystemTime = _SYSTEMTIME ptr -18h
CODE:004029EC
CODE:004029EC push ebp
CODE:004029ED mov ebp, esp
CODE:004029EF add esp, 0FFFFFFE8h
CODE:004029F2 lea eax, [ebp+SystemTime]
CODE:004029F5 push eax ; lpSystemTime
CODE:004029F6 call GetSystemTime
CODE:004029FB movzx eax, [ebp+SystemTime.wHour]
CODE:004029FF imul eax, 3Ch
CODE:00402A02 add ax, [ebp+SystemTime.wMinute]
CODE:00402A06 imul eax, 3Ch
CODE:00402A09 xor edx, edx
CODE:00402A0B mov dx, [ebp+SystemTime.wSecond]
CODE:00402A0F add eax, edx
CODE:00402A11 imul eax, 3E8h
CODE:00402A17 mov dx, [ebp+SystemTime.wMilliseconds]
CODE:00402A1B add eax, edx
CODE:00402A1D mov ds:dword_4AA044, eax <-- En este punto se guarda el milisegundo en la posicion semilla
CODE:00402A23 mov esp, ebp
CODE:00402A25 pop ebp
CODE:00402A26 retn
CODE:00402A26 XXX_InicializaSemilla endp


3) Probamos a meter la inicialización de la semilla cada vez que pedimos un numero.

00402BFC 60 PUSHAD
00402BFD 9C PUSHFD
00402BFE E8 E9FDFFFF CALL WanCatan.004029EC
00402C03 9D POPFD
00402C04 61 POPAD
00402C05 6915 44A04A00 >IMUL EDX,DWORD PTR DS:[4AA044],8088405
00402C0F F7E2 MUL EDX
00402C11 8BC2 MOV EAX,EDX
00402C13 C3 RETN


Nos damos cuenta de que esto realmente no funciona, se debe a que no pasa tiempo suficiente para que se generen numeros distintos, con lo cual los dados nos producen el mismo resultado :/

4) Vamos a meter el codigo de inicialización de la semilla justamente antes de la tirada de dados, no hay mucho espacio así que elegimos algun sitio donde podamos mover o borrar instrucciones sin dañar el funcionamiento del programa.
Yo en concreto he elegido unas posiciones donde se definían estaticamente 3 valores:

004751F7 B2 00 MOV DL,0
004751F9 E9 8C020000 JMP WanCatan.0047548A
004751FE 90 NOP


0047541C B2 01 MOV DL,1
0047541E 90 NOP
0047541F 90 NOP
00475420 90 NOP
00475421 90 NOP

0047542E B2 02 MOV DL,2
00475430 90 NOP
00475431 90 NOP
00475432 90 NOP
00475433 90 NOP

--> 0047548A Insertamos nuestro codigo
0047548A 8BC7 MOV EAX,EDI
0047548C 60 PUSHAD
0047548D E8 5AD5F8FF CALL WanCatan.004029EC
00475492 61 POPAD
00475493 ^E9 67FDFFFF JMP WanCatan.004751FF

00475498 E8 E7FCFFFF CALL WanCatan.00475184
0047549D C3 RETN
--


Con esta modificicación ahora cada vez que se realice una tirada de dados la posición de memoria "semilla" se reinicializará con los milisegundos actuales obtenidos de la hora del sistema.

comentarios:

Uchiha Itachi dijo...

¿Podrias pasarme tu exe modificado?