Log in

View Full Version : How to implement


friedo
December 13th, 2004, 14:07
Hello.

I have a function f(x)=y while x and y are 16 bit values. (see list)
It seems to be something with shift and xor operations. Is there any way to find an acceptable function for this instead of saving all 65536 solution words?
Any Ideas are welcome...
Regards,
friedo


x = f(x)
00 00 = 2F 57
01 ec = ad 50
08 c5 = 16 df
0e 70 = 17 2c
0f 23 = 8e a0
14 D5 = B3 63
15 1A = B2 AC
18 8d = 4c f1
1F 0C = 61 09
1f 38 = 11 1c
21 74 = E2 1A
21 a9 = c7 73
29 6a = bb ed
2b 10 = aa 93
2c 80 = 97 44
2c ad = 51 92
2d 10 = cb ca
30 27 = f3 f2
32 CD = 0E 9E
32 E8 = 82 26
33 9a = e3 4b
37 d5 = d6 49
39 28 = F6 B1
3b fe = 07 ad
41 45 = 11 45
4A 0C = 65 5B
4d a4 = 86 41
53 78 = 70 63
54 2B = 74 0A
58 E5 = A2 4D
5B B1 = 1B 8F
5c 13 = ef e7
5d 71 = 61 22
5D C5 = 82 62
60 CD = B7 5A
6B CB = BB 1A
6f 63 = d4 a7
73 c8 = 8e 26
77 4f = 06 3c
79 6e = 6c 7e
7b 50 = 5b 71

dELTA
December 13th, 2004, 15:13
Where did you get these numbers? If they are from a program you have, just debug it and reverse the code of the algorithm directly. If the numbers are in a cycle (or rather just unique for all inputs), you might be lucky and it being an LCG (linear congruential generator), and in that case you can break it easily. I would have tried that in a blackbox situation anyway.

friedo
December 13th, 2004, 15:29
Quote:
[Originally Posted by dELTA]Where did you get these numbers? If they are from a program you have, just debug it and reverse the code of the algorithm directly. If the numbers are in a cycle, you might be lucky and it's an LCG (linear congruential generator), and in that case you can break it easily. I would have tried that in a blackbox situation anyway.


No, these numbers are from an "unknown blackbox".

I already tried some possibilities like rotate left/xor for 16 bit keys and every shiftlength but get no solution which is acceptable for all values. til now i only have unique values!(but i have to get them manually and this takes long time so may be there are some values which are not unique...)

anyway, may be i write a little generator to test other things too...

nathan
December 14th, 2004, 03:26
Quote:
[Originally Posted by dELTA]Where did you get these numbers? If they are from a program you have, just debug it and reverse the code of the algorithm directly. If the numbers are in a cycle (or rather just unique for all inputs), you might be lucky and it being an LCG (linear congruential generator), and in that case you can break it easily. I would have tried that in a blackbox situation anyway.


Hi Delta,

do you have any pointer to attacking LCG ?

Thnx,

nathan

dELTA
December 14th, 2004, 04:10
Sorry, I meant LFSR (Linear feedback shift register), which can be easily fully reversed with the Berlekamp-Massey algorithm. LCGs are weak too though, but I'm not sure if there is any deterministic algorithm to reverse their parameters directly from any output stream. Can you clear it up Mike?

friedo
December 14th, 2004, 04:16
Here you find a nice sample of that LSFR:
http://ihome.ust.hk/~trippen/Cryptography/BM/frameset.html

naides
December 14th, 2004, 09:17
Can you post a series of Consecutive values of x, with the corresponding f(x)?

Finding patterns,if any, is easier that way.

Also,

Graph the function, and see clusters and trends,

Also, if you try two the same x more than once, you get the same f(x) right???

mike
December 14th, 2004, 16:24
Neither LFSRs nor LCGs have any input, so the function can't be either of those. It might be a linear function. You can test for linearity like this:

1. Collecting 16 input-output pairs,
2. Write them as rows of a 16x32 binary matrix
3. Then row-reduce. This will give you an xor pattern for each of the 16 bits.
4. Check against some more input-output pairs: take the patterns corresponding to each input bit and xor them together. They should match the output.

If that's the case, then you only need to store 16 patterns instead of 2^16.

However, it's likely that it's a nonlinear function. All nonlinear functions on 16 bits can be written as polynomials over GF(2^16) or over integers, but you may end up storing 2^16 coefficients, so there's no guarantee it'll take up less room.

You can test to see if it's an nth order polynomial by taking points x1, x2, ..., xn, calculating the polynomial f(x) = (x-x1)(x-x2)...(x-xn) and seeing if the rest of the points fit what you have so far.

BTW, This is the basis of secret splitting: for a 3/2 split (3 total shares, any 2 of which give a solution), choose three points f(a),f(b),f(c) on a cubic curve and make a fourth point f(d) be the secret key.

f(a),f(b) first share
f(b),f(c) second share
f(c),f(a) third share

Only when two players get together can they fit the cubic to the points and calculate f(d).

dELTA
December 14th, 2004, 16:32
Quote:
Neither LFSRs nor LCGs have any input
I was thinking that the LFSR och LCG would be reseeded with the input each time, but come to think about it that really doesn't make much sense. I guess I was drunk or something, sorry.

nikolatesla20
December 15th, 2004, 09:23
Holy cow mike, how did you get so good with these maths

I tell ya...I need to go back to school some more. I can write unpackers but crypto is so hard to wrap my head around sometimes.

Well, gotta start somewhere..

-nt20

JMI
December 15th, 2004, 12:54
It might be because "holy cow mike" may just happen to have some connection with crypto in his "real" life. And, unlike some of us who flunked out of math in the third grade (what do you mean "divide" the number, is that like cutting it with a knife?), he actually may use some of this stuff, as well as understand it.

Of course, on the other hand, he could just be completely wierd and actually LIKE math. Over my long and useless life I've actually heard rumours that there are such people. I might actually have talked to one or two, without realizing it, because, of course, I would have had no idea what they were talking about.

But even if I have no idea what the heck they are talking about, I am glad they keep using those numbers and crazy symbols and "stuff" to keep explaining how the universe actually works and to make "stuff" that makes life easier for those of us who aren't bright enough to actually "get it."

Of course it's all "relative."

Regards,

nikolatesla20
December 15th, 2004, 14:10
Yes, I'm sure Mike uses this stuff a lot for his daily routine, of course I realize that..

prolly a good uni degree too.

-nt20

mike
December 15th, 2004, 16:24
JMI got it: I like math. Here's an example:

The cross product of two vectors is proportional to the area they sweep out, so the cross product of any vector with itself is zero. The cross product only exists in three dimensions, but a generalization called the wedge product, denoted /\, exists in all dimensions. The wedge product of any vector with itself is also zero.

When dealing with the cross product, people often use x,y,z or i,j,k as the directions. With the wedge product, they just use the letter e with a subscript: e_1, e_2, ..., e_i, ..., e_n.

Finally, there's a field of mathematics called differential geometry; here the vectors are called "differential forms".

Now I can tell you a pun I made up:

Old MacDonald had a form: e_i /\ e_i = 0

gabri3l
December 15th, 2004, 16:53
Oh boy Mike now you started with math puns.
This one is borrowed from a Foxtrot comic.

Quote:
M(2.71828)r^2 (1/y) ^-1 sqrt(x^2)(force/acceleration)

JMI
December 15th, 2004, 17:41
Alright now, you people cut that out. I already explained that there are those of us who can't speak "math." I can sing the Inchworm Song, from the movie "Hans Christian Anderson" though. No wait, most of you weren't born when that was in the Theaters.

Regards,

mike
December 15th, 2004, 19:44
I saw it on the Muppet show:
"Inchworm, inchworm,
measuring the marigolds,
you and your arithmetic
will probably go far.
Inchworm, inchworm,
measuring the marigolds,
seems to me you'd stop and see
how beautiful they are!"

And the "powers of 2 chorus"
2 & 2 are 4
4 & 4 are 8
8 & 8 are 16
16 & 16 are 32
(repeat)

I'd always take it out to 2^16, but it never quite fit the meter.

Quote:
[Originally Posted by 'gabri3l']M(2.71828)r^2 (1/y) ^-1 sqrt(x^2)(force/acceleration)

How apropos that we have Gabriel announcing Merry Christmas!

JMI
December 15th, 2004, 20:16
That's the one. And, now that you've "translated" gabri3l's clever Merry Christmas, I actually do see it.

Now if we could only get everyone to understand the concept of "Peace on Earth and Good Will to Everyone," in whatever language they may speak or understand, then we'd really have something going.

Regards,

Woodmann
December 15th, 2004, 22:45
Ya know,

I can remember when I said, "when the hell will I ever need to use this math shit in real life". They said "take calculus, it will be good for you".
What a bunch of bullshit until, holy o fuck, I get a job that actually requires such knowledge.

Thankfully there are quick reference manuals for us "power lamers" .

Anyway, I love to read the posts in this crypto forum, it helps me to realize that there are still somethings that will always be important

Woodmann

Silver
December 16th, 2004, 07:30
http://www.sosmath.com. That's all I have to say on the matter

JMI
December 16th, 2004, 12:58
The only time I can remember actually using my high school trig was when I was trying to figure out the "exact" angle of the meeting of two walls in my kitchen as part of a remodeling project I was building. It was not "square" and "something less than 90 degrees, and I had a fairly expensive countertop being made and I wanted it to fit "exactly." So I dug out the old trig book and worked it out.

Of course, the fabrication shop then cut it wrong, twice. They didn't make any money on that project. And, of course, the long wall was not straight and I ended up floating out that wall to make it "appear" level. Sometimes it IS just easier to tear the thing down and start with new wood. After 40 years, things start to get all bent out of shape. Even people.

Regards,

volodya
December 17th, 2004, 14:32
Sorry, I meant LFSR (Linear feedback shift register), which can be easily fully reversed with the Berlekamp-Massey algorithm. LCGs are weak too though, but I'm not sure if there is any deterministic algorithm to reverse their parameters directly from any output stream.

http://www.uni-mainz.de/~pommeren/Kryptologie/Bitstrom/2_Analyse/LCGcrack.html