| |
 |
|
|
Science Forum Index » Cryptography Forum » Generating a short GUID from varying input formats
Page 1 of 1
|
| Author |
Message |
| Jeff Ishaq |
 Posted: Wed Jan 28, 2004 3:55 pm |
|
|
|
Guest
|
Hey folks. I'm trying to generate a global unique ID (GUID) for a
Treo 600 smartphone, as part of a registration key generation process.
The CDMA version of the smartphone reports a UID in the format of
"600BC01G", and the GSM version of the smartphone reports a UID of
"EAFMD23230093". As far as I know, the length of these two respective
strings is constant.
I'd like to minimize the number of alphanumeric characters the user
must enter into the key generation program to reduce the likelihood of
miskeying (and the subsequent bunk registration code, email from upset
user, and regeneration of a new key). A GUID of 8 or fewer
alphanumeric characters would be great.
How can I generate a short GUID, given either of the two UID formats
noted above as an input, that is globally unique across both formats?
In other words, the GUID generated from a CDMA-format UID string
("600BC01G") must never conflict with the GUID generated from a
GSM-format UID string ("600BC01G"), and vice versa.
Hopefully these makes the problem simpler:
1) I will never need to work backwards from the GUID to the original
UID string
2) The number of alphanumeric characters in the resulting GUID can
vary, as long as it's 8 or fewer chars.
I poked around on this group, and it seems I would first want to
compress the input string to shorten it, and then perform a hash on
the output. The trick seems to be ensuring the string compression
can't produce a conflict between any possible CDMA-style UID string
and any possible GSM-style UID string.
I sure never took any classes that covered this... can someone kindly
point me in the right direction here?
Please followup to the group, as I have abandoned using a real email
address for usenet postings. Thanks very much,
-Jeff |
|
|
| Back to top |
|
| Roger Schlafly |
| Posted: Wed Jan 28, 2004 5:05 pm |
|
|
|
Guest
|
"Jeff Ishaq" <ishaqjunk@hotmail.com> wrote
Quote: I poked around on this group, and it seems I would first want to
compress the input string to shorten it, and then perform a hash on
the output. The trick seems to be ensuring the string compression.
if you use a secure hash, like sha1, then you can skip the compression.
it does no good. |
|
|
| Back to top |
|
| Ernst Lippe |
| Posted: Thu Jan 29, 2004 6:18 am |
|
|
|
Guest
|
On Wed, 28 Jan 2004 12:55:52 +0000, Jeff Ishaq wrote:
Quote: Hey folks. I'm trying to generate a global unique ID (GUID) for a
Treo 600 smartphone, as part of a registration key generation process.
The CDMA version of the smartphone reports a UID in the format of
"600BC01G", and the GSM version of the smartphone reports a UID of
"EAFMD23230093". As far as I know, the length of these two respective
strings is constant.
I'd like to minimize the number of alphanumeric characters the user
must enter into the key generation program to reduce the likelihood of
miskeying (and the subsequent bunk registration code, email from upset
user, and regeneration of a new key). A GUID of 8 or fewer
alphanumeric characters would be great.
How can I generate a short GUID, given either of the two UID formats
noted above as an input, that is globally unique across both formats?
In other words, the GUID generated from a CDMA-format UID string
("600BC01G") must never conflict with the GUID generated from a
GSM-format UID string ("600BC01G"), and vice versa.
Hopefully these makes the problem simpler:
1) I will never need to work backwards from the GUID to the original
UID string
2) The number of alphanumeric characters in the resulting GUID can
vary, as long as it's 8 or fewer chars.
I poked around on this group, and it seems I would first want to
compress the input string to shorten it, and then perform a hash on
the output. The trick seems to be ensuring the string compression
can't produce a conflict between any possible CDMA-style UID string
and any possible GSM-style UID string.
From a theoretical point of view, the problem, as you stated it,
cannot be solved by any mathematical function. The number of possible
different inputs is larger than the number of outputs so there must be
different inputs that will generate the same output.
From a practical point of view, your real problem is probably
solvable, but you will need to give more information about what you
are trying to achieve.
First of all, why don't you simply use a database? This is probably
the most robust solution to prevent duplicate GUID's.
When you cannot use a database, you will either have to know more
about the possible set of UID's or you will have to accept a (small)
risk of getting duplicates.
It seems unlikely that the number of possible UID's is larger than the
number of 8 char GUID's. If you know the system that is used to
generate the UID's (e.g. that the initial characters are constant or
are chosen from a small set) it might be possible to find some
function that produces unique GUID's. But unless you can get
authoritive information about the internal structure of the UID's,
this is a tricky approach, because at some point in future the
manufacturer might decide to change the UID generation procedure.
With all other solutions you will have a small risk of generating
duplicate GUID's. The best approach probably is to use a
cryptographical hash function on the UID's and use that to generate
the GUID. The risk of getting a duplicate GUID is very small, but of
course it will increase when the number of smartphones increases. When
the number of smartphones is equal to the square root of the total
number of possible GUID's (in this case that would be more than 36^4 =
1679616) you have a 50% chance that there is at least one duplicate
GUID.
BTW, what are the security requirements for your system
(after all, this is sci.crypt).
Ernst Lippe |
|
|
| Back to top |
|
| |
|
Page 1 of 1
All times are GMT - 5 Hours
The time now is Fri Oct 10, 2008 8:35 pm
|
|