PDA

View Full Version : Random Number Analysis


akimp3
April 15th, 2002, 19:15
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.
Thanks in advance

Kythen
April 15th, 2002, 22:24
Quick question for you on your password generation method...

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

mike
April 15th, 2002, 23:08
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.

foxthree
April 16th, 2002, 06:43
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

Solomon
April 16th, 2002, 07:26
CryptGenRandom() from MS Crypto API may also work.

akimp3
April 16th, 2002, 11:11
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 .
thanks in advance

akimp3
April 16th, 2002, 18:12
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

mike
April 16th, 2002, 21:26
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

akimp3
April 17th, 2002, 11:26
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
times for each passwords.If you need anymore info please tell
me and i will try to gather them.
thanks

Snatch
April 17th, 2002, 14:38
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

Dimedrol
April 17th, 2002, 14:52
Hi

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

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.

akimp3
April 18th, 2002, 11:18
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
passwords?
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
I have learned a lot about this but these question are
still emberassing me.
thanks in advance

akimp3

Dimedrol
April 18th, 2002, 12:07
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
passwords?
>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

106 220 7344 7877 ( from your list of passwords )
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.

Hope I answered all your questions.

Regards, Dimedrol.

akimp3
April 18th, 2002, 18:43
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?
s you know in later passwords there is many that follow your rules(divisibale by 10).

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.
could you please tell me more about Blum-Blum-Shub generator.
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

mike
April 18th, 2002, 19:12
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?

akimp3
April 18th, 2002, 20:09
Hi Mike
thank you for replying to my questions.
Finally something that i know appear in this
thread.I know RSA very well(to my knowledge),i have used
it a lot of time.As i told you my first project is to prove to my
boss that these random numbers are week.I think afer all your
(Dimdrol,you and others) help i am very close to it.
The secont project is to give him(my boos) a good random
generator.I have thinked to use the RSA method described
in chapter 5 of applied cryptography handbook.
But before this i have to prove to my boss that the current
algo used by his sister is really bad.
The divisability rules found by dimdrol was very good
because i could use it to show to my boss that I can find the
next password with 10 hope in the worst case,but as you have seen I have found a contradiction to it.
So i have to use another rule.
If you know anything that could help me please help me.
I have another question from you how did you find the LGC of
Delphi?

thank you very much for your help

akimp3

radiant
April 18th, 2002, 20:13
Handbook of Applied Cryptography
h**p://www.cacr.math.uwaterloo.ca/hac/

See Chapter 5 for BlumBlumShub

And a C implementation is here:
h**p://www.mindspring.com/~pate/crypto/chap05/blumblum.c

radiant

mike
April 18th, 2002, 20:46
Quote:
the differences between sequential seeds are
not ALWAYS divisible by 10.


So what? If you know one of them, then skip 9, generate four passwords, and test them. You expect to get it on the tenth, but sometimes it'll be a little different. Once you find which of the four work, skip 9 from that one and try again. Even in the worst case where you don't know the original seed, you only have to test 2 billion passwords (2^31). Depending on how long the test takes, it could be as little as an hour to try all possible passwords.

Even if you didn't know how the passwords were generated, their length is too short: trying 10^14 different numbers= 2^46 is very doable.

I looked up delphi random on google and poked around. 0x8088405+1 has a period of about 2^32 and is used all over the place, especially in Zip encryption.

Again, you aren't going to get a secure system by accident. There are lots of ways to attack systems that most people don't even think of. What are you trying to protect with these passwords? Are you going to store them somewhere? How is that database protected?

akimp3
April 19th, 2002, 08:01
Hi
thanks for your reply .
about the project:
the project is for the Telephone company.They will sel phone card
with this passwords.Each person after picking up a public telephone will here a message that asks for the password
then he have to dial the password ,if he dial a valid password
he can dial any number he want.As you see if this password
are regenerable my boss will dye because our company has
investigated on this project.
For the bruteforce that you sayed ,it is impossible because
10 password is resonable to try on the phone but 40(4*10)
is impossible.I have to give them a solution that is resonable.
the seed is changed between 10 and 100 so if I add 9 and generate 4 password i have to do this 10 time in the worst case
that gives me 4*10 password(not resonable).Correct me if I
have not understand what you mean by adding 9 and generating 4 passwords.
About the storage the passwords will be encrypted and stored
in an oracle database.No one will have access to them,and the encryption is done by the encryption library of oracle 9i.

thank you very much for your help,you teach me a lot of
great things i really apreciate you.

thanks

akimp3

Dimedrol
April 19th, 2002, 08:38
Hi akimp3

Yes I knew what those differences between sequential seeds are not _always_ divisible by 10 ( it's seen from my example with seeds 66921289 and 66920498 ).
That's why I said:
"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."

Let's make a statistical analysis of differences between sequental seeds.

For the example ( these are not a real numbers, just for the illustration ):
differences
30, 70, 50, 100, 31, 50, 30, 70, 62, 40, 80, ....

It's seen what there are much more neighbour differences which are divisible by 10 than others.

To calculate exact probability of getting the next difference divisible by 10 we need to know the full set of differences, but even without knowing that, from the statistical analysis we can see what this probability is higher than 1/2 which is _very_ good ( in casino for example chances to win are much less ).

And besides, you can find the next password not only in direct order, but in a reverce order also.

I mean if you've found the seed say 66923456 - you can do 2 passes - in a direct order
66923456 + 10, 66923456 + 20, 66923456 + 30, .. 66923456 + 100
and in a reverse order
66923456 - 10, 66923456 - 20, 66923456 - 30, ... 66923456 -100

BTW: I think range 10 - 100 between seeds is too strict. I think it's possible to reduce it ( but you need to gather more statistics ).

So you see - max. 20 hops (can be reduced I think) ( 10 in direct order and 10 in reverse order ) and you get a password _with_a_very_good_probability ( again )

Regards, Dimedrol.

akimp3
April 19th, 2002, 18:03
Hi
Dimedrol thank you very much for your help.
here are more statisticd. I have find something in them
but i am not sure if it usable.
Download the attached text file.the file has all the passwords
and their seeds in front of them.
As you have told me the seeds are divisble by 10 in most case.But after a number of password the (difference-1) is
divisible by 10.And after that the other passwords seeds are
divisible by 10 since we arrive to another KEY password that
the seed difference is not divisible by 10 and (difference-1)
is ivisible by 10.I have tried to find the number of ordinary password between two KEY password.We can not count
the first transition because we dont know maybe there is other
passwords before it that have 5 as their last digit.
but after that there is:
15 number with 6 at their end
17 number with 7 at their end
15 number with 8 at their end
19 number with 9 at their end
18 number with 0 at their end
Do you think that a rule exist between this numbers?

thanks in advance

akimp3

mike
April 20th, 2002, 18:58
How do you think telemarketers call people? By hand? If you know one seed that generates a number, you can set up a war dialer to try every seed after that until it finds one. According to the list below, you'd have to try at most 100.

akimp3
April 20th, 2002, 19:56
Hi
thank to all of you that helped me on this project
specially Mike and Dimedrol.
I have shown the program to my boss and he has
accepted that the algo is week.He asked me to write
him a random number generator.Without your help
i will never arrive to this point.
This board,its moderator and all of its members are greats.
if I had asked for help on other boards they would
not have helped me and they would have treated me as person
who ask for cr*ck. But here you have teach me a lot
of thinks you have answered to all my stupids questions
and you solved my problem.

Thank to all of you
I will never forget your help

akimp3