Random Number Analysis

[akimp3]

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]

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]

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]

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]

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]

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]

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]

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