TR Forums

So apparently my brain isn't working well today... ...and it's been many years since I went through my linear algebra class. I am trying to find the inverse the following transform.

L(m)=m ^ (m << 6) ^ (m << 10)

Where ^ is XOR and << is rotate left.

What's sad is even my Google fu is failing. If someone wants to flat out give the answer, fine, but I'd rather and explanation or a pointer to an explanation.

--SS

You have the value for L(m) and you want to find the value for m?

Can you explain what you mean by 'rotate left'? Is this like an integer bit-shift, or like a clockwise rotation?

You may not be able to -- XOR is generally not onto or one-to-one.

ie, x^y = 1111 works with x = 1010, y = 0101 or x = 1100, y = 0011 or x = 1001, y = 0110.

To even try and say more than that I'd also need to know what you mean by "rotate left."

For the rotate left, m << 1 shifts all bits left one position with the MSB becoming the LSB. 1100b << 1 = 1001b.

Yes, you have the value of L(m) and need to solve for m. This transform is from a substitution, permutation block cypher. In order to implement the decryption, I have to work out the inverse of the SP block and hence the inverse of this transform.

--SS

I have the same concern as SNM with inversing the XOR; you're sure there's a unique solution? I hoping there's something with the three shifts (where the first m is shifted zero positions) that reduces the number of possibilities so there is a unique solution. How many bits does m have?

Maybe I'm missing something you've figured out already. It may help if you explain how you're casting this as a linear algebra problem.

Are there any constraints on the input? 32-bit input? Is there a possibility that some of the most/least significant bits are known to be zero?

Oh, wait, I bet it's 16-bit input. So the left-most bit in the original number is XORed with the bit in position seven (from left) and position 11 to get the output's bit. So:
(ry = result bit position y, numerals stand for the bit position from left, 1-based indexing)
r1 = 1 ^ 7 ^ 11
r2 = 2 ^ 8 ^ 12
r3 = 3 ^ 9 ^ 13
r4 = 4 ^ 10 ^ 14
r5 = 5 ^ 11 ^ 15
r6 = 6 ^ 12 ^ 16
r7 = 7 ^ 13 ^ 1
r8 = 8 ^ 14 ^ 2
r9 = 9 ^ 15 ^ 3
r10 = 10 ^ 16 ^ 4
r11 = 11 ^ 1 ^ 5
r12 = 12 ^ 2 ^ 6
r13 = 13 ^ 3 ^ 7
r14 = 14 ^ 4 ^ 8
r15 = 15 ^ 5 ^ 9
r16 = 16 ^ 6 ^ 10

Now XOR is the inverse of itself, so to find the actual value of bit one we need to XOR r1 with the actual values of bits 7 and 11.
1 = r1 ^ 7 ^ 11
1 = r1 ^ r13 ^ 13 ^ 3 ^ 11
1 = r1 ^ r13 ^ r3 ^ 9 ^ 11
1 = r1 ^ r13 ^ r3 ^ r15 ^ 15 ^ 5 ^ 11
Hey look, 15 ^ 5 ^ 11 = r5.
1 = r1 ^ r13 ^ r3 ^ r15 ^ r5.
I just got all these by looking.

Wash, rinse, and repeat. There is almost certainly a sequence of bit shifts and XORs on the result that will have the same outcome, but I can't summon up the math to prove it directly right now, if I ever knew it. But once you work out all the equations you can probably come up with them anyway, and they will then be immediately obvious and intuitive.

EDIT: Wow, this stuff becomes a lot more fun once out of college. I think I just spent an hour on that.

wibeasley wrote:

I have the same concern as SNM with inversing the XOR; you're sure there's a unique solution? I hoping there's something with the three shifts (where the first m is shifted zero positions) that reduces the number of possibilities so there is a unique solution. How many bits does m have?

Maybe I'm missing something you've figured out already. It may help if you explain how you're casting this as a linear algebra problem.

It turns into a system of linear equations (that should be independent if I didn't miss something) with n equations for an n-bit number (m0m1...m_n) with each equation of the following form:
m0^6^10,
m1^7^11,
m2^8^12,
...
m_n-10^n-4^m_n
...
m_n^5^9
= L(m)
where n is the number of bits and m is the value (I left off the 'm' prefix after the first as a shorthand)

Hope that helps (and that I didn't go crazy somewhere on my math).

edit: SNM's solution is the kind I went with first, but here's the 'linear algebra' approach

arsenhazzard wrote:

edit: SNM's solution is the kind I went with first, but here's the 'linear algebra' approach

Same approach, I just solved it for a specific n and didn't dress it up in generalized language/notation because I didn't realize they would be independent in the general case, being a bit slow.

It is 16 bits wide. Here is the whole block cypher.



K1 through K4 are 16 bit keys which are disjoint subsets of a larger 64 bit key .

That's cool, I wish I knew more about cryptology. Thanks guys for spelling out the linear equations. I'm curious. If the length of m was an arbitrary/unsepcified number of bits, does anyone have a feeling if a unique solution would exist? If it was longer than 16 bits, you'd need more XORs and shifts, right?

I'm in the middle a software implementation of the large encryption algorithm of which that cypher is a part. There is a very interesting job opening here in town for a system engineer/programming type. It is what my degree is in and I really enjoy it, but unfortunately my professional resume is all IT type stuff. So I figure I need to "go the extra mile" to get notice. Once I have it working in software (C), I'm going to due an implementation in Verilog.

BTW, I feel like a real idiot now as the inverse transform was actually printed in one of the papers I'm reading. For those that are interested...

L(m) = m ^ ( m << 6 ) ^ ( m << 10 )
L'(m) = m' ^ ( m' << 2 ) ^ ( m' << 4 ) ^ ( m' << 12 ) ^ ( m' << 14 )

--SS

SecretSquirrel wrote:

I'm in the middle a software implementation of the large encryption algorithm of which that cypher is a part. There is a very interesting job opening here in town for a system engineer/programming type. It is what my degree is in and I really enjoy it, but unfortunately my professional resume is all IT type stuff. So I figure I need to "go the extra mile" to get notice. Once I have it working in software (C), I'm going to due an implementation in Verilog.

BTW, I feel like a real idiot now as the inverse transform was actually printed in one of the papers I'm reading. For those that are interested...

L(m) = m ^ ( m << 6 ) ^ ( m << 10 )
L'(m) = m' ^ ( m' << 2 ) ^ ( m' << 4 ) ^ ( m' << 12 ) ^ ( m' << 14 )

--SS

I am surprised that has a unique solution. I would have expected it to be irreversible like the result of a modulus operation because of the XOR operator.

Shining Arcanine wrote:

I am surprised that has a unique solution. I would have expected it to be irreversible like the result of a modulus operation because of the XOR operator.

It's because it's doing two XORs on the original number, just displaced. There's no data destruction -- otherwise it wouldn't be a very good cipher!

Did the paper give you a proof or anything, Squirrel? I saw that pattern in the equation I solved but figured there had to be a more elegant derivation of it.

Nope. No proof. The paper is an analysis of the larger algorithm so the implementation discussion is purely to show what is being talked about. Now I just have to figure out how to undo the XOR at the beginning of the block.

--SS

Wow, this is pretty old but I'm bored...

I don't think any cipher can destroy any data as one of the basics is f'( f(x) ) = x (must be invertible; wouldn't be useful if even intended receiver can't figure out what the secret message was) and you can't reconstruct original data from nothing... (at the simplest, what if you just burn the secret message? safe but again not very useful).

The system of equations were getting somewhere but doesn't seem to state lower 6-bits of m and m' are actually the same and that is what make this very easy to solve (0-base indexing, mi = ith bit of m):



m'0 = m0 ^ 0 ^ 0 = m0 (or m0 = m'0)
m'1 = m1 ^ 0 ^ 0 = m1
m'2 = m2 ^ 0 ^ 0 = m2
m'3 = m3 ^ 0 ^ 0 = m3
m'4 = m4 ^ 0 ^ 0 = m4
m'5 = m5 ^ 0 ^ 0 = m5

m'6 = m6 ^ m0 ^ 0 = m6 ^ m0 (or m6 = m'6 ^ m0 = m'6 ^ m'0)
m'7 = m7 ^ m1 ^ 0 = m7 ^ m1
m'8 = m8 ^ m2 ^ 0 = m8 ^ m2
m'9 = m9 ^ m3 ^ 0 = m9 ^ m3

So to get up to 10-bits of original value:


m'10 = m10 ^ m4 ^ m0 (or m10 = m'10 ^ m4 ^ m0 = m'10 ^ m'4 ^ m'0)
m'11 = m11 ^ m5 ^ m1

To get up to 12-bits of original value:


m'12 = m12 ^ m6 ^ m2 (or m12 = m'12 ^ m6 ^ m2 = m'12 ^ m'6 ^ m'0 ^ m'2; m6 = m'6 ^ m'0 so we need an extra m'0 term)
m'13 = m13 ^ m7 ^ m3
m'14 = m14 ^ m8 ^ m4
m'15 = m15 ^ m9 ^ m5 // after this, we'll need to XOR more shifted terms since once again m6 will need to be derived, should be fine for 16-bits with maybe & 0xFFFF for safe measure

To get up to 16-bits of original value:

Lans wrote:

I don't think any cipher can destroy any data as one of the basics is f'( f(x) ) = x (must be invertible; wouldn't be useful if even intended receiver can't figure out what the secret message was) and you can't reconstruct original data from nothing... (at the simplest, what if you just burn the secret message? safe but again not very useful).

At a glance, it looked like a hash function, which lacks the property of bijection.

I am not sure if it looked like a hash function as I didn't see a variable length string to fixed length output...

Anyways why I bother posting to this thread is, in addition to be being bored, at a glance I didn't buy the inverse function:

L(m) = m ^ ( m << 6 ) ^ ( m << 10 )
L'(m) = m' ^ ( m' << 2 ) ^ ( m' << 4 ) ^ ( m' << 12 ) ^ ( m' << 14 )

Namely, I see (m & 0x3F) ^ 0 ^ 0 based only left shifts of 6 and 10 so (m' << 2) and (m' << 4) looks very odd. Lets try:

L(15) = 15 ^ (15 << 6) ^ (15 << 10) = 15 ^ 960 ^ 15360 = 16335
L'(16335) = 16335 ^ (16335 << 2) ^ (16335 << 4) ^ (16335 << 12) ^ (16335 << 14) = 16335 ^ 65340 ^ 261360 ^ 66908160 ^ 267632640 = 202116099 and if you only take the lower 16-bits, 3,075

So lets try what I proposed:
L'(m') = m' ^ (m' << 6) ^ (m' << 10) ^ (m' << 12)
M'(16335) = 16335 ^ 1045440 ^ 16727040 ^ 66908160 = 51118095 (lower 16-bits is indeed 15)

Shining Arcanine wrote:

At a glance, it looked like a hash function, which lacks the property of bijection.

Not necessarily; XOR preserves information, and (assuming that L(m) has the same number of bits as m) there very well could be a 1-to-1 mapping of values. Hash functions generally reduce the number of bits by a some large factor; that does not appear to be the case here.

just brew it! wrote:

Shining Arcanine wrote:

At a glance, it looked like a hash function, which lacks the property of bijection.

Not necessarily; XOR preserves information, and (assuming that L(m) has the same number of bits as m) there very well could be a 1-to-1 mapping of values. Hash functions generally reduce the number of bits by a some large factor; that does not appear to be the case here.

<A> XOR <A> = 0, for all <A> in W.

If I do <A> XOR <A> for some <A> and tell you the result, can you tell me which <A> I used?

Now that I think about it, there is a contradiction in saying that a ^ (a <<n) = 0 where n > 0 and a is non-zero, which can be used to prove that the result zero only occurs when a = 0, but I neither had the time to consider it then nor do I have the time to do it now that have considered it. It also would need to be generalized to repeated XORs and it is not clear to me that such a thing is possible in all cases.

<A> XOR <A> is not a hash function either, since (as you've pointed out) it always results in zero.

<A> XOR <C> (where C is a known constant) preserves information.

As another interesting example, consider the swapping of two variables without the use of a temporary -- the following sequence will swap the contents of the variables <A> and <B>, and would not be possible if XOR destroyed information:

Shining Arcanine wrote:

Now that I think about it, there is a contradiction in saying that a ^ (a <<n) = 0 where n > 0 and a is non-zero, which can be used to prove that the result zero only occurs when a = 0, but I neither had the time to consider it then nor do I have the time to do it now that have considered it. It also would need to be generalized to repeated XORs and it is not clear to me that such a thing is possible in all cases.

Does anybody even know what this paragraph means?
Let's try out a = 10101010b and n = 2.
a << 2 = 10101010
a ^ (a<<2) = 10101010 ^ 10101010
a ^ (a<<2) = 0.

But I'm not sure what this even applies to in the discussion above, is anybody else?

just brew it! wrote:

<A> XOR <A> is not a hash function either, since (as you've pointed out) it always results in zero.

<A> XOR <C> (where C is a known constant) preserves information.

As another interesting example, consider the swapping of two variables without the use of a temporary -- the following sequence will swap the contents of the variables <A> and <B>, and would not be possible if XOR destroyed information:

Code: Select all

<A> := <A> XOR <B>
<B> := <A> XOR <B>
<A> := <A> XOR <B>

<A> XOR <A> is a hash function; there is no logical law that states that hash functions must have desirable properties. See the description at Wikipedia:

A hash function is any well-defined procedure or mathematical function that converts a large, possibly variable-sized amount of data into a small datum, usually a single integer that may serve as an index to an array (cf. associative array).

http://en.wikipedia.org/wiki/Hash_function

As for XOR, under certain circumstances, XOR destroys information. Under other circumstances, it preserves information. It is like asking whether or not e^(at) and e^(bt) are linearly independent. They are linearly dependent when a = b and linearly independent in all other cases.

SNM wrote:

Shining Arcanine wrote:

Now that I think about it, there is a contradiction in saying that a ^ (a <<n) = 0 where n > 0 and a is non-zero, which can be used to prove that the result zero only occurs when a = 0,

Let's try out a = 10101010b and n = 2.
a << 2 = 10101010
a ^ (a<<2) = 10101010 ^ 10101010
a ^ (a<<2) = 0.

I suspect a confusion between the different meanings of the << operator. In the original question it has been defined as Rotate Left so a << 2 = 10101010, however in C it is defined as Shift Left so a << 2 = 1010101000 which if stored in an 8 bit identifier would be a << 2 = 10101000.

notfred wrote:

SNM wrote:

Shining Arcanine wrote:

Now that I think about it, there is a contradiction in saying that a ^ (a <<n) = 0 where n > 0 and a is non-zero, which can be used to prove that the result zero only occurs when a = 0,

Let's try out a = 10101010b and n = 2.
a << 2 = 10101010
a ^ (a<<2) = 10101010 ^ 10101010
a ^ (a<<2) = 0.

I suspect a confusion between the different meanings of the << operator. In the original question it has been defined as Rotate Left so a << 2 = 10101010, however in C it is defined as Shift Left so a << 2 = 1010101000 which if stored in an 8 bit identifier would be a << 2 = 10101000.

That would be my fault. I mistook the original poster's operator definitions for the typical information that I usually have to provide to mathematics majors when describing computer calculations, so I did not realize that the original poster was redefining the << operator. With that mistake, my brain misinterpreted the original poster's equations as having C-style expressions.

Shining Arcanine wrote:

<A> XOR <A> is a hash function; there is no logical law that states that hash functions must have desirable properties. See the description at Wikipedia:

A hash function is any well-defined procedure or mathematical function that converts a large, possibly variable-sized amount of data into a small datum, usually a single integer that may serve as an index to an array (cf. associative array).

It may be a hash function by strict definition, but it is not a useful hash function.

Shining Arcanine wrote:

just brew it! wrote:

<A> XOR <A> is not a hash function either, since (as you've pointed out) it always results in zero.

<A> XOR <C> (where C is a known constant) preserves information.

As another interesting example, consider the swapping of two variables without the use of a temporary -- the following sequence will swap the contents of the variables <A> and <B>, and would not be possible if XOR destroyed information:

Code: Select all

<A> := <A> XOR <B>
<B> := <A> XOR <B>
<A> := <A> XOR <B>

<A> XOR <A> is a hash function; there is no logical law that states that hash functions must have desirable properties. See the description at Wikipedia:

A hash function is any well-defined procedure or mathematical function that converts a large, possibly variable-sized amount of data into a small datum, usually a single integer that may serve as an index to an array (cf. associative array).

http://en.wikipedia.org/wiki/Hash_function

As for XOR, under certain circumstances, XOR destroys information. Under other circumstances, it preserves information. It is like asking whether or not e^(at) and e^(bt) are linearly independent. They are linearly dependent when a = b and linearly independent in all other cases.

jbi was implying that XORing with a known constant does not destroy information, that is a true statement. You were pointing out that if you XOR something with itself you get 0, this is also a true statement, but if your function is f(x) = x XOR C, and you say f(A) = 0, then I know that A = C, the "function" f(x) = x XOR x is identical to the zero function and so isn't in any real sense the XOR function, you are simply describing a property of the zero function.

First things first, I'll admit that my inverse function would not work for "rotate left" in original post but I did prove "left shift" and "rotate left" requires different inverse function (by example).

Now on to why I really want to reply (now, yeah, I didn't feel like replying just to point out the obvious from above), strictly speaking h(x) = 0 is still a hash function albeit it is not useful at all... imagine a hash table with that for index!

Given the context we are discussing this, this would be more appropriate: http://en.wikipedia.org/wiki/Cryptograp ... h_function

And it would totally fail:

it is infeasible to modify a message without hash being changed,
it is infeasible to find two different messages with the same hash.

Yes, it would not be invertible and it is actually something desirable for cryptographic hash function (preimage resistance) but probably impossible (just because I don't want to prove it) to simultaneously meet the requirement of being a "useful" hash function also.