|
private string GetUniqueKey()
{
int maxSize = 8 ;
int minSize = 5 ;
char[] chars = new char[62];
string a;
a = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890";
chars = a.ToCharArray();
int size = maxSize ;
byte[] data = new byte[1];
RNGCryptoServiceProvider crypto = new RNGCryptoServiceProvider();
crypto.GetNonZeroBytes(data) ;
size = maxSize ;
data = new byte[size];
crypto.GetNonZeroBytes(data);
StringBuilder result = new StringBuilder(size) ;
foreach(byte b in data )
{ result.Append(chars1)>;); }
return result.ToString();
}
i have to use it for my project.... wen i ran this code i got an error in the 'foreach' loop...
the error is coming on the... result.append(chars1)>;); line..
please let me know wot the error is and how i can solve it....
thanks..
|
|
|
|
|
i have a gridview which is storing a record .i want to generate a unique no while saving one record.
the format should be like (pscode(2place),year(4place)and num(4place))
example:- 01-2007-0001
where ps_code is char(2),
year comes form date-which is of date and time datattype
and the last 4 place are char(4),
where ps_code and date are the field of my data base.i want retrive ps_code and year from my database to generate the unique number.
can tell me how will i do it?
i am devloping a web applcation where the backend is vb.net2005.
|
|
|
|
|
I beleive that it would be a better approach with the collision with seeded values would make the collisions negligible.
|
|
|
|
|
I'm missing something here. Do you mean that it would be better to use a truncated SHA or MD5 hash? I'm certainly no mathmatician but I'm guessing that the number of collisions would increase dramatically by truncating all but the first 8 bytes. Since my mind struggles with things it can't visualize, somebody let me know if my statement is incorrect so I can revise my world a little.
|
|
|
|
|
Perhaps I made an error, but after generating 100,000 hashes from DateTime.Now I got 100,000 collisions on SHA1 and 99,999 with MD5 using only the first 8 characters. Here is the method, tell me if my method is flawed:
<br />
int coll = 0;<br />
List<string> hashs = new List<string>(); ;<br />
string hashed;<br />
<br />
for (int i = 0; i < 100000; i++)<br />
{<br />
MD5CryptoServiceProvider crypto = new MD5CryptoServiceProvider();<br />
byte[] buffer = ASCIIEncoding.ASCII.GetBytes(DateTime.Now.ToString());<br />
<br />
byte[] hash = crypto.ComputeHash(buffer);<br />
<br />
hashed = hash.ToString().Substring(0, 8);<br />
<br />
if (hashs.Contains(hashed))<br />
coll++;<br />
<br />
hashs.Add(hashed);<br />
}<br />
And then I did the exact same thing with SHA1CryptoServiceProvider.
p.s. pardon the poor variable names and generall messiness, I did not spend much time on this.
|
|
|
|
|
This is more along the lines of what I would expect. It's not so much your code but your expectation. Unlike an encryption algorithm, a hash is designed to create the same number from the same data every time. Since you are making hashes from sequential data, the first part of the hash is going to be the same. Try the last 8 characters.
Even using the last eight, you will still get numerous collisions.
One more thing. The way .net works, a tight loop like that may be returning the same datetime value throughout the entire 99,000 iterations. Since .net likes to get ahead of itself, you could try throwing in a small delay.
SHA256, 384 & 512 are much stronger than MD5 in terms of encryption but we're not really encrypting; we're just trying to generate random unique id's.
As I recall, when you first started, you were using random numbers rather than timestamps. If you're going to use a hash, I would stick with the random numbers.
You could also consider using a key generation algorithm. This way, your invoices could be self-validating. Again, it's not really extreme security but it's kinda cool. That way, if somebody tried to guess an invoice number, they would have had to use a key generator with the same algorithm and password.
|
|
|
|
|
If you are using the key to protect sensitive data, this is a misapplication. Even casual crackers won't be put off by a 64 bit key. Inexpensive computers can easily handle the number of permutations required to create a collision. Just look at how long it took to generate 100,000 keys.
Sensitive data should be protected by a login system using strong passwords and encryption. AES, Blowfish, and Twofish seem to be the best. The database record itself can be linked to the login account so even if a cracker could create a collision, they still couldn't access the data.
On the other hand, if the objective is to create unique transaction ID's, it doesn't matter if they're sequential because they shouldn't be guarding the data. You could use a random increment value to leave "holes" in the sequence but even that wouldn't matter.
If you want something that looks more unique than '1234567' (the Spaceballs password), you can use a combination of a serial number, date, customer ID, time, random machine state, and a CRC (to validate). With a little work, this can be kept to 8 printable bytes. Also, consider using bit flags and different generation methods. For instance, bit 0 of byte 3 could indicate a different sequence to the bytes. The date and time are going to be the most unique portions of the key.
Another approach is to pre-compute sufficient unique keys to cover anticipated transactions. This way, you can eliminate collisions up front and identify anything that looks sequential. The assignment code simply picks an unassigned number from a database. You could even randomize that process if you wanted.
These are practical approaches to the problem that don't place undue expectations on the results. I'm sure there are thousands of coders and mathematicians that can come up with more unique and inventive approaches than this. My point is that there is a conflict in the basic premise: an 8 byte printable key code cannot provide significant data security no matter how random.
|
|
|
|
|
Thanks alot, Very good insight.
|
|
|
|
|
This is a silly article. I suppose I can think of various reasons where a pseudo-unique number would be useful, but this certainly isn't one of them.
There is a perceived security benefit, but it's "security by obfuscation", which is weak, to say the least.
However, if that were the purpose, then looking for an algorithm that has the provides the best distribution is unnecessary. Conflicts will exist and thus must be handled. And since they are handled, the scope of the conflicts are relatively immaterial.
|
|
|
|
|
Kasajian, I would agree that the basic premise of this article isn't a useful application but it could certainly provide useful information for someone else with a similar question. I have seen this type of question several times (and even had it myself several years ago). The answer to the question is simple: it's not needed. But, the article is valuable for anyone thinking that they are providing security by using a pseudo-random number. I can say that attackers as a whole are more versed in security than the average software developer. Developers need to become much more knowledgeable in encryption, validation, and security than they are now. Even Microsoft gets hacked on a regular basis.
For anyone reading this thread, it is important to understand that as computers become more powerful, hackers' abilities to crack code and leap firewalls increases. MD5 used to be considered secure. It probably shouldn't even be used anymore. Digital signatures can be faked and even strong encryption can be broken if the user doesn't take specific precautions. There is an entire community out there dedicated to "reverse engineering" and they are pretty smart folks.
|
|
|
|
|
yeah and then I get the .NET reflector from aisto.com and All your Base are belong to me! hehe.
|
|
|
|
|
Yup. For every lock there's a lock-picker. Paranoia is getting the best of me. Gotta go to my bomb shelter now.
|
|
|
|
|
From my reading of this article you want to
(1) create a short unique key
(2) make it difficult to guess this key given previous keys
An easy solution that would give you these properties is a linear congruential generator (which are often used for quick and dirty random number generators) see http://en.wikipedia.org/wiki/Linear_congruential_generator
You choose a seed (that is only know to you), then each time you call MyRandom.Next you get another number that you have not had before (because of the special choice of constants m and c). Given that no-one knows your seed or the exact method or even more than a handful of keys it would be unlikely that a casual observer would crack your pattern.
<br />
public class MyRandom : Random<br />
{<br />
public MyRandom(int seed)<br />
{<br />
this.seed = (ulong)seed;<br />
}<br />
<br />
private ulong seed;<br />
const ulong m = 1664525;<br />
const ulong c = 1013904223;<br />
<br />
public override int Next()<br />
{<br />
unchecked<br />
{<br />
seed = seed*m + c;<br />
}<br />
<br />
return (int)(seed & 0xFFFFFFFFu);<br />
}<br />
}<br />
This will generate uint.MaxValue (or about 4,000,000,000) unique keys before duplication. In addition it will be very fast (a 64 bit multiply, add, mask and cast for each new number).
What do you think?
|
|
|
|
|
Good one But what if my web application restarted?
|
|
|
|
|
You could always save the last used seed.
|
|
|
|
|
Hou could you make sure that the newly-generated result would not duplicate the second last result or the first result?
|
|
|
|
|
did you notice that the characters you generate randomly are not evenly distributed? you have a charset and you index it by using a random number from 0 to 255 % charset.length - 1. if you count the random numbers which result in charset[0] and compare it to the count of random numbers resulting in charset[charset.length - 1] you will notice, that the latter is less by 1. by the way, you dont have to convert the string to a char[], you can index it directly: a[index]. i also read that you intended to make random unique keys to prevent an attack. neither are these keys unique nor are they suited to prevent an attack. you should rely on authentication to do that.
|
|
|
|
|
Thanks for your comments. But i dont want to produce evenly distributed random numbers? Oth erwise they will become sequence not random numbers. Secondly I am not using this technique to replace authentication. There are sites where you dont even have login facility that is no authentication at all, like hotel web booking engines where you can input your booking number to see details of your booking. In such situations you can use this algo to generate part of booking number which you want to be unique.
|
|
|
|
|
evenly distributet does not mean "sequence". 1 2 3 4 5 6 7 is a sequence, but if you create 10^6 numbers using your algorithm you will notice that some chars appear more frequently than others. considering that you want your keys to be unguessable you should ensure that nobody can make conclusions about whether a specific number is likely to exist or not. look for example at binary numbers where the probability for "1" ist 90%. an attacker using brute force would now try numbers with more ones first in order to correctly guess a number more early. as a solution i would simply recommend using an instance of system.random which has a nice overload: Next(0,charset.length); there may now be critics saying that the built-in random functionality does not generate good (preudo-)random numbers. i doubt that it will make a difference in this scenario.
const int MinLength = 5;
const int MaxLength = 8;
const string CharSet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890";
static Random m_Rand = new Random();
public static string CreateRandomKey()
{
int length = m_Rand.Next(MinLength, MaxLength + 1);
StringBuilder key = new StringBuilder(length);
for (int i = 0; i < length; i++)
{
key.Append(CharSet[m_Rand.Next(0, CharSet.Lenmgth)]);
}
return key.ToString();
}
|
|
|
|
|
You could use a shortened GUID. Part of the GUID is made up from the Interface MAC address. if you don't need uniqueness between different hosts it may help
|
|
|
|
|
The reason your key generation did not have duplicates has less to do with it being a better algorithm, and more to the number of bits of information held by the key.
If I'm reading your code correctly, the key is 8 tokens from a set of 62. 62^8 ~= 2^48 -- approximately the same key space as a 48 bit number. [NOTE: Case sensitive keys are going to confuse users who type 'm342z' instead of 'M342z' -- I'd recommend droping the case sensitive tokens, and just make the length longer to make up the loss of the extra bit from each character.]
Using approximations for the birthday paradox, to get a duplicate 50% of the time on a random key in key space size of N, you need to generate about e^( ln(N) / 2 ) keys. In concrete terms, for your 32 bit keys, you get 50% at about 60000. For your RNG cryto algorithm with 48 bit numbers, you need about 15,000,000.
Neither 32 or 48 bits seem to be particularly secure. Why not just use sequence number? A hostile program is going to compromise your system anyway. On the other hand, if you want security, you'll want to bump up the number of bits to 56 at bare minumum, and the more the better. The RNG algorithm you present should otherwise be okay, assuming no security holes are found in the .NET crypto RNG classes or algorithms.
For 56 bits, dropping your case-sensitive tokens (using 0-9 and A-Z), you'd need about 11 tokens in your string. I guess it all depends on how much security you need in your web application.
|
|
|
|
|
why did you think :
Guid.NewGuid().ToString().GetHashCode().ToString("x");
would guive a unique number?
when you do ".ToString()" you transform your guid to a string so you could just as well take "hello world" or any other string.
"GetHashCode" is not used for truly unique values , its used to get a number that can be used in hash algorithms eg. when inserting the item into a hashtable, where you indeed have collisions.
(which the .net hashtable handles by storing key value pairs where the hashcode collieds in a list in the same bucket.... )
so it has nothing to do with unique numbers.
|
|
|
|
|
Back in the olden days (1980's) we used hash codes to create faster database indexing. We could count on a collision every once in a while so we did the same thing MS does; we checked the table.
Why not simply apply randomness to a sequential order? Mathematically, it is impossible to avoid collisions given a number with this set of permutations. If you think of a seeded system that addresses points on a euclidian plane, it would be relatively easy to create a token that is both unique and random. This would guarantee uniqueness that the modulus hash math cannot.
Here's a "seed" for an idea:
The "plane" is a representation of your token universe placed in
some unique order like this:
0akL|U4yr<br />
t2iZ|8wTK<br />
ou1R|qcHm<br />
A9Wh|eQzP<br />
----+----<br />
If6s|YMCx<br />
qNdX|ESgj<br />
B7vh|l3bG<br />
nJ5S|DFVO
This plane would be represented by the string:
"0akLU4yrt2iZ8wTKou1RqcHmA9WheQzPIf6sYMCxqNdXESgjB7vhl3bGnJ5SDFVO"
Sequentially, all the possible keys are represented by a base 64 number like this:
123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz (or whatever)
1. Randomly select one of the 4 quadrants of a plane<br />
2. Randomly select a direction (clockwise or counter-clockwise)<br />
3. Compute a radian from a pre-selected center that is <br />
n+x of the previous seed:<br />
Where: n is the previous seed (stored so your web server could crash:()<br />
x is a bounded random number<br />
4. Compute a random point described somewhere along the arc created by <br />
the radian within the selected quadrant<br />
5. Repeat steps 1, 2 and 4 8 times
Look at this as a random spiral through all the points in the plane. (Since it's a finite plane you will have to adjust for the "corners".) It's relatively random but since it increments or decrements sequentially, it's unique. I'm sure there is a flaw in my thinking but in theory, this should work fairly well with no collisions.
Eventually, you would traverse the entire universe, generating keys that could be ordered into a sequential list. It's just that the order in which you generate the keys is random. If I'm not mistaken, you would have to readjust your radians in a very limited increment to make sure you traverse every possible path. Someone smarter than I can probably tell you how to do this mathematically. As a matter of fact, I'm sure there is a theorum or something that covers what I've just described.
Please note that you can introduce additional randomness by the manner in which you arrange the "plane". The number of ways you can arrange the plane is the same as the permutations for the key itself. This would make it extremely difficult for someone to randomly select a matching key even if they know your methodology. They might be able to guess the correct direction, the radian and even the seed but can they guess where you placed all of the tokens in the plane?
The three downsides to this that I can see are:
1. You need to maintain your "seed"<br />
2. You have to maintain a fixed plane (you can't move the tokens<br />
around on the plane without creating the possibility of a collision.)<br />
3. I don't know how to represent this mathematically
Could someone that understands this type of math please comment on the weaknesses?
|
|
|
|
|
I just thought of an easier method of stating what I described in the previous comment. It would be easier to code from this.
Devise a method for calculating each possible permutation in a perfect sequential order. In other words, permutation number X =
X | Permutation
--+------------
1 | "AAAAAAA1"
2 | "AAAAAAA2"
3 | "AAAAAAA3"
. . .
n | "zzzzzzzz"
Etc.
Step 1: Calculate X based on previous seed so that you don't traverse the same path more than once
Step 2: Calculate permutation X
The difficult part is step 1. Applying geometry again, maybe this could be done using slopes of a curve. (I never was very good at the rubix cube.) Somehow, the seed has to be incremental in some fashion but describe a non-incremental curve through 8 tokens.
Another thought would be a parabola series because then you could use hashing algorithms. As you approach the vertex, the numbers would appear more sequential but as you move out, they become increasingly harder to guess without knowing the exact vertex. Even so, it would be easy to calculate the vertex given a few points so that may not be the best idea unless you can somehow assign the 64 tokens in the large end of the plane. I think I just lost myself.
-- modified at 14:04 Monday 19th June, 2006
|
|
|
|
|
Are you sure your keys are unique?
It seems to me that they are just very unlikely to be duplicates. The possible exception is using your RNGCryptoServiceProvider, which may be using some sort of internal sequential seeding formula... but then... when the system restarts, there is no permanent track of this seed...
I'd either use an auto-increment field, or at least check against a log of which keys have been used.
If you're generating large amounts of these, then maybe something similar to the RNGCryptoServiceProvider can be found, which could take the last generated key as a seed, thus guaranteeing continuation in the mathematical sequence, rather than claiming "random" to be the same as "unique".
---
I'm thinking of a song or two, a boy a girl and a rendezvous.
|
|
|
|
|