Hi

Now to the puzzle.

I have a hardware ID (Khw), that is generated from 8 different pieces of
hardware: Khw1 - Khw8.

I want to allow say 2 of the 8 hardware to change, and still be able to get
back to the original hardware id (Khw). And I only want to store the hash
value of Khw.

Is such a thing possible?

From:	Sebastian Gottschalk
Subject:	Re: Hardware ID
Date:	Thu, 20 Jan 2005 13:08:54 +0100

Karsten wrote:

> I want to allow say 2 of the 8 hardware to change, and still be able to get
> back to the original hardware id (Khw). And I only want to store the hash
> value of Khw.
>
> Is such a thing possible?

Renormalize the hardware component information to a GF(2^n) and use an
error correction code with Hamming distance of 5.
--
Dieser Schrieb stellt eine private Meinungsäußerung des Verfassers im
Sinne der gesetzlich garantierten Meinungsfreiheit dar. Wem das nicht
passt, der wende sich an das Bundesverfassungsgericht. Viel Erfolg!
Key: 0xA0E28D18 FP: 83AE 1136 1E2B 9767 8FB2 7594 4128 1A9E A0E2 8D18

From:	Karsten
Subject:	Re: Hardware ID
Date:	Thu, 20 Jan 2005 15:09:30 +0100

> Renormalize the hardware component information to a GF(2^n) and use an
> error correction code with Hamming distance of 5.

Would you mind be a little more detailed, I'm sorry but I don't understand
it

From:	Sebastian Gottschalk
Subject:	Re: Hardware ID
Date:	Thu, 20 Jan 2005 15:32:36 +0100

Karsten wrote:

>> Renormalize the hardware component information to a GF(2^n) and use an
>> error correction code with Hamming distance of 5.
>
> Would you mind be a little more detailed, I'm sorry but I don't understand
> it

At first you need to convert your hardware information to a binary
representation of all the same length n. Then you can create an error
correction code, which corrects up to 2 errorness elements or up to 2n bits
-- therefore, if you change just two elements of the codeword, it will
still map to the same codeword by applying the error correction, but will
map to another codeword if 3 or more elements get changed. The final
codeword can be hashed to prevent retrival of the actual information.

X=MD5(errorcorrect(maptobitstring(hardwaredata)))

Example:

Let's say we want to have 7 elements which can just two states (hardware
inserted or not inserted), and just one exchange is allowed. We encode them
as codewords of a (7/4)-Hamming Code.

i=0000 -> c=0000000
i=0001 -> c=1101001
....

Then we create the mapping of codeword->corrected codeword.
c=1101001 -> e=1101001 (c=e)
c=1111001 -> e=1101001 (c=e -> one bit changed)
c=1101000 -> e=1101001 (c=e -> one bit changed)
....
c=1101010 -> e=0101010 (c=e -> two bits changed -> other codeword)
--
Dieser Schrieb stellt eine private Meinungsäußerung des Verfassers im
Sinne der gesetzlich garantierten Meinungsfreiheit dar. Wem das nicht
passt, der wende sich an das Bundesverfassungsgericht. Viel Erfolg!
Key: 0xA0E28D18 FP: 83AE 1136 1E2B 9767 8FB2 7594 4128 1A9E A0E2 8D18

From:	Karsten
Subject:	Re: Hardware ID
Date:	Fri, 21 Jan 2005 09:31:06 +0100

First thank you very much for your explanation!

> At first you need to convert your hardware information to a binary
> representation of all the same length n.

Fine I was thinking of taking the MD5 of all single IDs, giving me 8 values
each of 128bits.

>Then you can create an error correction code, which corrects up to 2
errorness elements or up to 2n bits

So I should get a error correction code that can correct upto 256 bit? Does
such one exists?
I know about the hamming code, but AFAIK it can only correct 1 or 2 bits.

From:	Joris Dobbelsteen
Subject:	Re: Hardware ID
Date:	Fri, 21 Jan 2005 12:55:25 +0100

"Karsten" wrote in message
news:g53Id.84420$Vf.3753592@news000.worldonline.dk...
[snip]
> So I should get a error correction code that can correct upto 256 bit?
Does
> such one exists?
> I know about the hamming code, but AFAIK it can only correct 1 or 2 bits.
>

I believe that really depends on how much error correction code you add. On
RAM for each 8-bit we add a 1-bit ECC. We read rows of 64-bit and add a
8-bit ecc. This allows, depending on the algorithm, to correct 1 and detect
2. Adding more ecc code would allow you to correct and detect more bits.
For RAM they decided to take a ballance between likelyness of an error and
cost. A 1-bit error might be relative likely, 2 is lot less likely, 3 is
getting very unlikely, so the current ECC will do in nearly all situations.

For example a Data-CD stores 2 KB of data and 1/2 KB of ECC (double compared
to RAM). This is because errors are very likely on a CD and you must be able
to correct more errors.

So if you add a lot of ECC you will be able to completely recover the
256-bit.

- Joris

From:	Sebastian Gottschalk
Subject:	Re: Hardware ID
Date:	Fri, 21 Jan 2005 14:25:49 +0100

Karsten wrote:

>>Then you can create an error correction code, which corrects up to 2
> errorness elements or up to 2n bits
>
> So I should get a error correction code that can correct upto 256 bit? Does
> such one exists?
> I know about the hamming code, but AFAIK it can only correct 1 or 2 bits.

Hamming Code is just a specialized BCH code with Hamming distance of 3 ,
Abramson code is a BCH code combining Hamming code and parity code to get a
Hamming distance of 4. Generalized BCH code can create every Hamming
distance you want, but might be no perfect codes.

However these are codes in GF(2^n), not GF(2^128), therefore you should
split up the Khw-values in 128 bits and group all bits at the same position
over all Khw values, apply a BCH with Hamming Distance of 5 (corrects up to
2 errors) to each group and concatenate the results. As long as up to 2 Khw
values change the will introduce a maximum of 2 bit errors per group, the
error correction will work and produce the same output.

The chances that 3 changing hardware IDs will match perfectly to leave
every group of bits just with two error are 75% per group, leading to a
total chance of (3/4)^128 ~ 1/2^53, the same effort as generating a 53 bit
collision in the hash function from which the hardware IDs were derived.
--
Dieser Schrieb stellt eine private Meinungsäußerung des Verfassers im
Sinne der gesetzlich garantierten Meinungsfreiheit dar. Wem das nicht
passt, der wende sich an das Bundesverfassungsgericht. Viel Erfolg!
Key: 0xA0E28D18 FP: 83AE 1136 1E2B 9767 8FB2 7594 4128 1A9E A0E2 8D18

From:	Paul Rubin
Subject:	Re: Hardware ID
Date:	20 Jan 2005 21:57:21 -0800

"Karsten" writes:
> I have a hardware ID (Khw), that is generated from 8 different pieces of
> hardware: Khw1 - Khw8.
>
> I want to allow say 2 of the 8 hardware to change, and still be able to get
> back to the original hardware id (Khw). And I only want to store the hash
> value of Khw.
>
> Is such a thing possible?

You mean you want a secret-sharing scheme? The usual way is with the
Lagrange interpolation polynomial. Do you know about that?

From:	Karsten
Subject:	Re: Hardware ID
Date:	Fri, 21 Jan 2005 09:23:06 +0100

> You mean you want a secret-sharing scheme? The usual way is with the
> Lagrange interpolation polynomial. Do you know about that?

No, I'm afraid not

From:	Paul Rubin
Subject:	Re: Hardware ID
Date:	21 Jan 2005 01:07:40 -0800

"Karsten" writes:
> > You mean you want a secret-sharing scheme? The usual way is with the
> > Lagrange interpolation polynomial. Do you know about that?
>
> No, I'm afraid not

I'm confused. Can you describe your problem more clearly? How exactly
is Khw computed from Khw1...Khw8? Are you saying you have to start out
with a specific Khw1...8 and a specific Khw, and then be able to swap
out Khw_n's? The most general case might be hopeless.

From:	Karsten
Subject:	Re: Hardware ID
Date:	Fri, 21 Jan 2005 10:43:19 +0100

> I'm confused. Can you describe your problem more clearly?

Of course :-)

I get 8 ids of some kind from different pieces of hardware and a few ID's
from registry CPU, MAC, Windows product ID, Windows installation time,
physical RAM, CD drive, soundcard and volume ID of drive C.

These 8 id's are concatenated and I get and MD5 hash, this is Khw.

I use key to encrypt M and store it on the hard drive. If say 2 hardware
id's changes, it should still be possible to decrypt M. It's another case
when more than 2 id's changes.

Khw1 to Khw8 are hashes of the 8 hardware ID's, they might not be needed,
but should be used to detect how many ID's that have changed. It's not
important to see what ID's have changed, even though this is a side effect.

From:	Sebastian Gottschalk
Subject:	Re: Hardware ID
Date:	Fri, 21 Jan 2005 08:14:01 +0100

Paul Rubin wrote:

>> I want to allow say 2 of the 8 hardware to change, and still be able to get
>> back to the original hardware id (Khw). And I only want to store the hash
>> value of Khw.
>>
>> Is such a thing possible?
>
> You mean you want a secret-sharing scheme? The usual way is with the
> Lagrange interpolation polynomial. Do you know about that?

I also thought about that but I wonder how it could be used to work as
supposed.
--
Dieser Schrieb stellt eine private Meinungsäußerung des Verfassers im
Sinne der gesetzlich garantierten Meinungsfreiheit dar. Wem das nicht
passt, der wende sich an das Bundesverfassungsgericht. Viel Erfolg!
Key: 0xA0E28D18 FP: 83AE 1136 1E2B 9767 8FB2 7594 4128 1A9E A0E2 8D18