1. ## Random Number Analysis

Hi
My company works on a debit card project.
They have generated 10000 test passwords and
my boss have asked me to test if the numbers are really random.
The passwords are composed of 14 numbers and each number(0-9)is generated by the random function of delphi, so for generating one password.
The random function is called 14 times subsequently for each password. They have given me 100 passwords to do the test. I have seen (by eye) that some numbers like 8 and 7 are present in all the passwords exept 12 passwords.
So I wish to find a way to test that, these passwords are really assigned randomly. How can I generate by a statistical analysis, 10000 passwords that contain, some of the passwords that they have generated. Could you please advise me on how to do this?
Is there any program to do this? Or I have to write one myself? Is there any documents, explaining technics for this type of analysys?
Some documents or links or tutorials are very appreciated.

Did you reseed the RNG before each digit was produced in the password? If not, that greatly reduces the effectiveness. For C++ at least, and I assume Delphi, Pascal, and most other languages... the built-in RNG is quite weak. Generally it only takes a 32-bit seed that can easily be brute-forced. Once you have the seed figured out, then you can run the RNG however many times you need to get all the digits you used in the password (provided you didn't reseed it between digits). Not a very random result, as you can see. I would advise using a better RNG like the FIPS standard.

As for your analysis problem, are you trying to analyze the randomness of the passwords you were given? Or are you trying to produce more passwords using the given set? It's a bit confusing from what you posted. I'm not up on my stats, so I don't really know what techniques there are. I'd just look at digit frequencies in relation to position and other things like that.

Hope that helps!
Kythen

3. ## entropy

Actually, it's probably only 31 bits. Given one 14-digit password, you have 14*log_2 10 = 46 bits. With 10 or eleven digits (=33 to 36 bits) you can find the seed and predict *all* the other passwords, like Kythen said. See the WinZip thread for a similar situation using C's rand() function. I think the two random number generators are identical.

4. ## Yarrow....

Hi:

Why don't you use really "strong" PRNG implementations like Yarrow. From what I see, it is pretty straightforward to use in C++ and you can avoid the "seeding" attack as Mike mentions very easily.

Signed,
-- FoxThree

5. CryptGenRandom() from MS Crypto API may also work.

Hi
thanks for your help as kythen and mike said ,i want to be able
to genereate all(near all) the password from the 100 password that i have.I am not the person who have to chose the random algo,
i know better way likr RSA,.... but somoene else has chosed this
way i have to prove to my boss that this algo is weak and the number could be generated by someone else.
Mike a Kythen could you please give me more details on how i have to brute force the seed?
I have to be able to cra*k this random generation algo .

7. ## here are the 100 password that i have

Hi
I have tried the attack described in the Zip thread(with some modifications like j=14,...)but it did'nt find the cipher.I have attached the 100 password that I have to this message please take a look and guide me.
thank you very much.
i am waiting for your help

8. ## just to make sure

I'll help if you'll answer some questions.

1. What was the exact delphi code that generated the numbers? There are a bunch of different random functions in delphi. (Once I get the brute forcer working you can use it on any set of passwords, BTW.) The TLCG is: seed = 0x8088405*seed+1

2. Are these the first four passwords? They all run together in the file.

630 112 7612 8278
831 208 1648 1787
472 682 3216 7536
814 370 7032 2202

Hi
thank you very much for your help.
the 4 passwords are not the firsts.
They have generated a sets of 10000 password and give
me 100 subsequent password from the middle.
I have not seen the code that generate the numbers,because
i have to act like a hac*er that did'nt know anything about
the code generation. But i know(social engenering)that she
has used the random function and that she had called it 14
me and i will try to gather them.
thanks

10. Ever hear of LCG? Linear Congruent Generator...seek and ye shall find. There is a lot of information about them out there but not too much useful. I learned after a lot of research how to reverse the random number generator. So if you have a LCG such as seed = a*seed+b you can choose other values of a and b such that the series goes in the exact opposite order. Dont ask me why I needed to do this it was for a game called Worms2 but thats a seperate story . Just research LCGs there is a lot of higher math involved but if you can brute force a seed(4 billion possibilities shouldnt be too hard) that fits the 100 numbers you have well then there you have it.

Snatch

11. Hi

>But i know(social engenering)that she has used the
>random function and that she had called it 14

The key word here is "she"

I've tried several approaches to get numbers from your post using Delphi's RandInt(10) function.
But finally I found what there is no single "9" digit in 100 14-th chars numbers.
So RandInt(9) has solved the problem

/////////////////////////////////////////////////////////////
#include <ostream.h>
#include <memory.h>

unsigned long seed = 1;

void srand(unsigned long newseed)
{
seed = newseed;
}

int rand(void) // the same as RandInt(9) in Delphi ( should have probably been 10 !
{
_asm
{
mov eax, 9
imul edx, seed, 0x8088405
inc edx
mov seed, edx
mul edx
mov eax, edx
}
}

int main(int argc, char* argv[])
{
for(unsigned long a = 2; a < 0xFFFFFFFF; a++)
{
if( rand() == 6 )
if( rand() == 3 )
if( rand() == 0 )
if( rand() == 1 )
if( rand() == 1 )
if( rand() == 2 )
if( rand() == 7 )
if( rand() == 6 )
if( rand() == 1 )
if( rand() == 2 )
if( rand() == 8 )
if( rand() == 2 )
if( rand() == 7 )
if( rand() == 8 )
{
cout << "Seed: " << a - 1 << endl;
}
srand(a);
}
cout << "finished" << endl;
return 0;
}
/////////////////////////////////////////////////////////////

For the first 6 numbers from your list I got:

630 112 7612 8278 seed = 66918095 (3FD16CF) - looks like Delphi's time
831 208 1648 1787 seed = 66918195
472 682 3216 7536 seed = 66918245
814 370 7032 2202 seed = 66918325
807 474 0308 0117 seed = 66918355
457 077 2866 6866 seed = 66918405

so original code probably is:
for( i = 0; i < 10000; i++ )
{
Randomize()
for(j = 0; j < 14; j++)
{
cout << RandInt(9);
}
cout << endl;
}

There are very good chances to reconstruct the whole sequence of numbers.

Regards, Dimedrol.

12. ## i have some question

Hi
first I want to thanks everyone that is helping me on this
problem.
1)
I want to know how did you figured out that the TLGC is
TLCG is: seed = 0x8088405*seed+1 ?
2)
how did you figured out that she has changed the seed after
each 14 number and not after each number?
3)
Is it possible to fint more than one seed for a sequence of
numbers?
4)
now that we know the seed has changed for each password
how should we know the value of the seed for the others
5)
is there anyway to find the other passwords or a percent of
them?
6)
why did you rewrite the random function in asm,could'nt you
use the random function of C instead?
I will be very happy if you answer this questions
still emberassing me.

akimp3

13. Hi akimp3

>1) I want to know how did you figured out that the TLGC is TLCG is: seed = 0x8088405*seed+1 ?

You told Delphi was used. This is a Delphi's random function.

>2) how did you figured out that she has changed the seed after
each 14 number and not after each number?

Just tried the simplest way. It worked.

>3) Is it possible to fint more than one seed for a sequence of
numbers?

Theoretically this is possible. But in practice I did not get any collisions.

>4) now that we know the seed has changed for each password
how should we know the value of the seed for the others
>5) is there anyway to find the other passwords or a percent of
them?

After several experiments one can see what sequential seeds deffers from each other by at least 10 and at most 100

Let's say we've found the seed for

seed = 66920498

Remember what the next password is
088 324 1611 5783

Using rand() and srand() functions from that C sources we can generate a sequence of passwords for

66920498 + 10 < seed < 66920498 + 100

/////////////////////////////////////////
for(unsigned long k = 66920498 + 10; k < 66920498 + 100; k++)
{
srand(k);
for(int l = 0; l < 14; l++)
{
cout << rand();
}
cout << " seed = " << k << endl;
}
/////////////////////////////////////////

We'll get
43182424006850 seed =66920508
.....
08832416115783 seed =66920528 Gotcha! 21 - th variant is right

Actually it's possible to optimize this algo even more.
Don't know why but the differences between sequential seeds are divisible by 10;

Let's try to use this:
Password = 837 767 6775 4118
seed = 66921289

/////////////////////////////////////////
for(unsigned long k = 66921289+ 10; k < 66921289 + 100; k+=10)
{
srand(k);
for(int l = 0; l < 14; l++)
{
cout << rand();
}
cout << " seed = " << k << endl;
}
/////////////////////////////////////////

25256318313171 seed =66921299
58626750762053 seed =66921309
82086201322024 seed =66921319 !! 3-d variant is right

So it's possible to say what if one knows 1 password - he can find the next sequental password in at most 10 hops with a very good probability.

> 6) why did you rewrite the random function in asm,could'nt you
use the random function of C instead?

It's a disassembled and a bit modified RandInt function of Delphi.
It's in asm just to speed up the process of finding seeds.

Regards, Dimedrol.

14. ## other questions

HI
Dimedrol thank you very much for answering my questions.
I was trying two find a relation between the sedds and I found
that: the differences between sequential seeds are
not ALWAYS divisible by 10.
630 112 7612 8278 66918095
831 208 1648 1787 66918195
472 682 3216 7536 66918245
814 370 7032 2202 66918325
807 474 0308 0117 66918355
457 077 2866 6866 66918405
664 766 8370 3744 66918445
657 861 2536 1650 66918475
540 054 4803 8565 66918505
532 158 7250 6371 66918535
758 857 5673 4258 66918575
641 042 7030 2164 66918605
633 145 1386 0070 66918635
610 376 2750 1467 66918635
826 175 0272 8245 66918706

As you see the difference between 66918706 and 66918635 is
71 that is not divisble by 10.With this do you think that
it is a good idea to use the optimized program you wrote or not?

my second question is :
what is a Blum-Blum-Shub generator?
as you know i am a newbie in crypto world and all i do
in this board is learning a lot from experienst crypto guys.
to what kind of problem it is applicable?,...

I want to say thanks to all of you especially Dimedrol and Mike
who teach me a lot of hings.

akimp3

15. ## BBS

BBS is a random number generator based on the same problem as RSA, namely factoring. Predicting the output will be as hard as breaking RSA.

There are a lot of pitfalls in using crypto however! I broke a system that used DES encryption because of improper key management. I was able to write a program that recovered the password faster than you can blink.

What exactly are you trying to accomplish?

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•