# PRNG based on REP STOS

unlike many others, REP STOS/MOVS instruction is very hard to emulate (see “self-overwritten REP STOS/MOVS, IDA-Pro 5.4 and Ko” post). at first sight it’s easy! live CPU continues executing overwritten command, right? so, take OllyDbg or IDA-Pro and write a plug-in to redesign the trace engine. if the tracer meets self-overwritten REP STOS/MOVS it memorizes it and continues executing like the real CPU does. it’s easy! what’s the problem?!

but, it’s more than meets the eye. CPU stops executing over-written REP STOS/MOVS in arbitrary moments. well, almost arbitrary. hardware interrupts force CPU to clean pipeline, stopping executing the overwritten REP STOS/MOVS command. internal CPU events also stop REP executing. different CPUs have different behavior (and different bugs :=).

this gives us… a very interesting pseudo-random number generator. if initial ECX is quite big, REP loop finishes with almost unpredictable ECX and the most interesting part is – our PRNG does not look like normal PRNG!!!

to prove it, I wrote a simple POC (plz, do not use it in commercial software, coz, due to CPU bugs sometimes it crashes with access violation or another exception, but in general it works, I’m working on the stable version now). download it and run.

the program allocates memory on the heap, copies self-overwritten REP STOSB code there, initializes ECX by 16Mb value, passes control to it and displays ECX. the point is – ECX is different every run.

my favorite Pentium-III 733 MHz Coppermine (my base PC) copies at least 64 Kb in average, see:

16685683 (91533 copied)
16575731 (201485 copied)
16755560 (21656 copied)
16770446 (6770 copied)
16670677 (106539 copied)
16759763 (17453 copied)

Pentium-4 3.2 GHz HT (my home file-server) shows pretty different result:

16044939 (00732277 bytes copied)
16777211 (00000005 bytes copied)
16777210 (00000006 bytes copied)
16777206 (00000010 bytes copied)
16777209 (00000007 bytes copied)
15788810 (00988406 bytes copied)

damn! sometimes CPU copies only 5 bytes!!! well, not “sometimes” – very often!!! it makes this trick not just PRNG, but… kind of fingerprints of CPU.

 

6 Comments

  1. This is a neat trick indeed, but it would be just one statistically lousy PRNG with an awful performance.

  2. agreed, but sometimes you need to hide PRNG and REP STOS/MOVS is hidden very well. also, it replaces srand( (unsigned) time( NULL )).

  3. It should depend not only of CPU but from many other things including motherboard, OS, drivers, number of running tasks etc. But anyway – very good discovery! At least we know that those results should not to be constant.

  4. Slava Salnikov

    I expected that for CPU with more than one core, the results would be even worse than for HT, but I was wrong.
    Core2Duo Т7300
    15903784 (873432 copied)
    15835130 (942086 copied)
    16529462 (247754 copied)
    16332977 (444239 copied)
    14744372 (2032844 copied)
    13661618 (3115598 copied)
    15870420 (906796 copied)
    Strange but HT technology is to blame here. :-)

  5. I tested this on several machines/OS and it seems more dependant on the environment than CPU itself. For example, on a xp 64bit Pentium D, the plot of sorted results was like an S-curve, while on a vmware inside the same machine, an almost horizontal line. :)

  6. agreed. I’m working on my VM Ware detector, based on REP STOS/MOVS. the only problem – false positive alarms. sometimes real hardware acts like VM Ware. trying to find a solution.

Leave a comment

Comments are closed.