Python for Reverse Engineering

[Brad Tilley]

A friend of mine wrote an algorithm that generates strings. He says that
it's impossible to figure out exactly how the algorithm works. That may
be true, but I think if I had enough sample strings that I could write a
program to identify patterns in the strings and then produce strings
with similar patterns. He disagrees with me. He gave me 100 strings to
analyze.

I wrote a script to read each string and build a list of characters
present. I've discovered that he only uses 20 alpha/numeric chars to
generate the strings and that each string sums up to a value between
1000 and 1200 when I assign each char in the string its ASCII value.

What else might I do to analyze these things? As it stands now, I can
generate an acceptable string on ever 100th attempt or so, but I'd like
to do better than this.

-b

[Mike Meyer]

Re: Python for Reverse Engineering

Brad Tilley <rtilley@vt.edu > writes:
[color=blue]
> A friend of mine wrote an algorithm that generates strings. He says
> that it's impossible to figure out exactly how the algorithm
> works. That may be true, but I think if I had enough sample strings
> that I could write a program to identify patterns in the strings and
> then produce strings with similar patterns. He disagrees with me. He
> gave me 100 strings to analyze.
>
> I wrote a script to read each string and build a list of characters
> present. I've discovered that he only uses 20 alpha/numeric chars to
> generate the strings and that each string sums up to a value between
> 1000 and 1200 when I assign each char in the string its ASCII value.
>
> What else might I do to analyze these things? As it stands now, I can
> generate an acceptable string on ever 100th attempt or so, but I'd
> like to do better than this.[/color]

Build a markov chain generator. Basically, build tuples of characters
of length N, and use those to index a dictionary containing a list (or
string) of characters that follow that list of characters in your
input strings. So, with N equal 2, and d[('a', 'b')] = ['c', 'd', 'e']
you'd know that the strings abc, abd and abe appeared in the text. To
gennerate a string, pull a random key from the dictionary, then choose
random characters from the list that the last N characters treated as
a tuple index in the dictionary. Larger values of N generate strings
that more closely resemble the input text.

Optionally, make the objects stored in the dictionary keep a count of
how many times each character appears, and choose one randomly
weighted by those counts.

I've got a markov chain generator that works on words if you really
want to see one.

<mike
--
Mike Meyer <mwm@mired.or g> http://www.mired.org/home/mwm/
Independent WWW/Perforce/FreeBSD/Unix consultant, email for more information.

[Michael Fuhr]

Re: Python for Reverse Engineering

Brad Tilley <rtilley@vt.edu > writes:
[color=blue]
> A friend of mine wrote an algorithm that generates strings. He says that
> it's impossible to figure out exactly how the algorithm works. That may
> be true, but I think if I had enough sample strings that I could write a
> program to identify patterns in the strings and then produce strings
> with similar patterns. He disagrees with me. He gave me 100 strings to
> analyze.[/color]

What input, if any, does the algorithm take? What are the strings
used for? Care to post the 100 strings so others can have a look?
[color=blue]
> What else might I do to analyze these things? As it stands now, I can
> generate an acceptable string on ever 100th attempt or so, but I'd like
> to do better than this.[/color]

Reading about cryptanalysis might prove fruitful. I suspect the
number of "impossible to figure out" algorithms is far less than
the number of algorithms whose developers initially made that claim.

--
Michael Fuhr

http://www.fuhr.org/~mfuhr/

[Brad Tilley]

Re: Python for Reverse Engineering

Michael Fuhr wrote:[color=blue]
> Brad Tilley <rtilley@vt.edu > writes:
>[color=green]
>>A friend of mine wrote an algorithm that generates strings. He says that
>>it's impossible to figure out exactly how the algorithm works. That may
>>be true, but I think if I had enough sample strings that I could write a
>>program to identify patterns in the strings and then produce strings
>>with similar patterns. He disagrees with me. He gave me 100 strings to
>>analyze.[/color]
>
>
> What input, if any, does the algorithm take?[/color]

I don't know, but I'm guessing that there is none.
[color=blue]
> What are the strings used for?[/color]

To unlock an application he wrote (software key).
[color=blue]
> Care to post the 100 strings so others can have a look?[/color]

I'd rather not do that.
[color=blue]
> Reading about cryptanalysis might prove fruitful. I suspect the
> number of "impossible to figure out" algorithms is far less than
> the number of algorithms whose developers initially made that claim.[/color]

I suspect you're right.

[Jeremy Bowers]

Re: Python for Reverse Engineering

On Fri, 05 Nov 2004 23:36:57 -0500, Brad Tilley wrote:[color=blue][color=green]
>> What are the strings used for?[/color]
>
> To unlock an application he wrote (software key).[/color]

Ah.

Tell your friend the usual order of business when cracking these apps is
to find the conditional that does the final check for validity and
hard-code it to true (or false or whatever). Ask him if he really thinks
he can do better than massive companies like Electronic Arts and the other
large gaming companies, which still routinely experience 0-day (or less!)
warezing of their works.

The only remotely foolproof way to secure an app is to require an online
component, and to check that part. But few apps can really reasonably do
that, and customers *do* notice.

I say this mostly because people should not fool themselves into thinking
they can make this work, when hundreds or thousands of others can try. If
your software can't profit without that kind of protection, it probably
can't profit with it, either.

(I've read several rants from shareware developers bemoaning the piracy
rate and complaining that while people pirate their work, nobody pays for
it. Inevitably, I dig deeper and find they are peddling Yet Another FTP
program or the like (HTML editor, XML editor, text editor, simple image
editor, image viewer, macro program, etc.), *which the market has clearly
set a value of $0 for*. This is off-topic, but I'd check this too; you may
be protecting something of no value on the open market. I don't know, but
based on my readings and a quick browse through Tucows, the odds are
pretty decent.)

[James Stroud]

Re: Python for Reverse Engineering

[color=blue][color=green]
> > Care to post the 100 strings so others can have a look?[/color]
>
> I'd rather not do that.[/color]

If your friend was worth his salt as an algorithm writer, he'd be more than
willing to let you post a mere 100 strings. For any good generator, this
would be paltry compared to the number of strings it would take to figure out
the algorithm.

But--he is probably making impossible claims here, anyway...
[color=blue]
> Reading about cryptanalysis might prove fruitful.[/color]

Perhaps your friend should pay heed to this as well.


James

--
James Stroud, Ph.D.
UCLA-DOE Institute for Genomics and Proteomics
611 Charles E. Young Dr. S.
MBI 205, UCLA 951570
Los Angeles CA 90095-1570

http://www.jamesstroud.com/

[Duncan Smith]

Re: Python for Reverse Engineering


"James Stroud" <jstroud@mbi.uc la.edu> wrote in message
news:mailman.60 42.1099806403.5 135.python-list@python.org ...[color=blue]
>[color=green][color=darkred]
> > > Care to post the 100 strings so others can have a look?[/color]
> >
> > I'd rather not do that.[/color]
>
> If your friend was worth his salt as an algorithm writer, he'd be more[/color]
than[color=blue]
> willing to let you post a mere 100 strings. For any good generator, this
> would be paltry compared to the number of strings it would take to figure[/color]
out[color=blue]
> the algorithm.
>
> But--he is probably making impossible claims here, anyway...
>[/color]

[snip]

Doesn't that depend on exactly what is meant by "figure out exactly how the
algorithm works"? If it means identify (with absolute certainty) the
algorithm used to generate the strings, then it surely can't be possible.

Duncan

[Brad Tilley]

Re: Python for Reverse Engineering

Duncan Smith wrote:[color=blue][color=green]
>>If your friend was worth his salt as an algorithm writer, he'd be more...
>>But--he is probably making impossible claims here, anyway...
>>[/color]
>
>
> [snip]
>
> Doesn't that depend on exactly what is meant by "figure out exactly how the
> algorithm works"? If it means identify (with absolute certainty) the
> algorithm used to generate the strings, then it surely can't be possible.
>
> Duncan[/color]

That's my thought as well. I don't want to know exactly how the
algorithm generates strings. But, I think that if I analyze enough
strings I should know, on some level, what an acceptable string looks like.

Samba coders never see Microsoft's file and print sharing source code,
yet they are able to emulate an NT server quite well just by observing
packets.

[Duncan Smith]

Re: Python for Reverse Engineering


"Brad Tilley" <rtilley@vt.edu > wrote in message
news:cmlj6b$7j9 $1@solaris.cc.v t.edu...[color=blue]
> Duncan Smith wrote:[color=green][color=darkred]
> >>If your friend was worth his salt as an algorithm writer, he'd be[/color][/color][/color]
more...[color=blue][color=green][color=darkred]
> >>But--he is probably making impossible claims here, anyway...
> >>[/color]
> >
> >
> > [snip]
> >
> > Doesn't that depend on exactly what is meant by "figure out exactly how[/color][/color]
the[color=blue][color=green]
> > algorithm works"? If it means identify (with absolute certainty) the
> > algorithm used to generate the strings, then it surely can't be[/color][/color]
possible.[color=blue][color=green]
> >
> > Duncan[/color]
>
> That's my thought as well. I don't want to know exactly how the
> algorithm generates strings. But, I think that if I analyze enough
> strings I should know, on some level, what an acceptable string looks[/color]
like.[color=blue]
>
> Samba coders never see Microsoft's file and print sharing source code,
> yet they are able to emulate an NT server quite well just by observing
> packets.[/color]

Right, so you might be able to come up with something that produces similar
output. Do you know if the strings are generated independently? If so,
there must be some stochastic component (or unknown inputs) or the strings
would be identical. How about the frequencies of the characters? Are some
(significantly) more frequent than others? Do some characters follow others
with unusually high frequency? Do characters tend to cluster (more or less
that you'd expect from independently generated characters)? Unless the
strings are very long you probably can't answer these questions too reliably
with only 100 strings.

Markov Chains are a possibility (as already mentioned). I'd probably start
by looking at the simpler things first. The 1000 to 1200 sum might be a
clue, particularly if you're having trouble emulating it. Of course, if
this turns out to be some sort of code and you're looking at some encoded
text, then that's something I know little about, and the above might be next
to useless.

Maybe the basic statistical tests in Gary Strangman's stats.py would be
useful, unless you already have R and RPy?

Duncan

[James Sapara]

Re: Python for Reverse Engineering

Well for the fun of it I'm gonna post 100 strings that are probably like
the strings referred to earlier. I'll answer a limited set of questions
about the keys if you want, but for the most part they are a set of 100
unqiue keys, with two variable inputs and a few static inputs.

#0 5V6XB-TV6N6-5H7J3-WWTWQ-6H74B
#1 CBPPC-LTJ5X-1S8ZS-5LVBZ-YRFVW
#2 QJCT6-VXYLT-2S9QZ-SQ02G-MJD9S
#3 SF46P-67SK3-6BWFD-BQ9Y0-XJ4J2
#4 ZR4VZ-BS499-TPMDT-Y2MBF-LN2VL
#5 YKR4K-ZNJ41-W2N2D-0G2FL-ZZSFK
#6 4ZBVQ-388NT-H7742-MM7N8-NYRSM
#7 468HK-3DX11-H13CD-MVPQL-N9G5K
#8 0W853-1V66Q-HPMHK-6H105-45LX1
#9 0XSRZ-1XW7N-H3LLK-620JR-4ND0J
#10 JF3XN-C7SCR-QBP0G-VQPJ2-0JG0G
#11 4BKKK-TZW8T-ZV713-80QB6-J8NV7
#12 R5W5D-V1YV8-83DRQ-DXTPX-9P7ZH
#13 C5S1Z-NJQMS-89JP0-45LVP-R7WY4
#14 CS3VY-L4SY9-1MPNM-50P0T-Y8GXX
#15 ZY7JC-P8KRK-K1511-80RZN-J8VQY
#16 KQ5D3-2F4P2-DRT19-347KH-K1R6Z
#17 KZ0ZH-QXC2Z-NH4WS-S9KDD-M0P7D
#18 5LLXY-G0GNY-F0GJW-KD1WH-8LL4Z
#19 5K7C3-G9VBQ-FBP3K-K43M5-81ZL1
#20 4TX4X-TJ8H6-Z5QTL-8F8RR-JSYCJ
#21 47LHR-TH59K-Z2Y8C-8XPL0-JPGD2
#22 DDK4B-YWD46-ZD123-3SGFQ-KX3FB
#23 4T8D6-346BS-HTM9C-MM17Z-NYL8W
#24 YTK41-ZH3H0-WKJTP-0Y3R9-ZWZCT
#25 JRH3Q-CF1HG-QYXMB-VRX4Y-0QTPP
#26 RL645-V06HF-807TF-DDTR1-9L7C8
#27 K66DH-Q3HPB-NJR1J-SH5KQ-M5C6B
#28 B6X7T-7RNKW-3S2MW-752K2-B7S6G
#29 CP30J-Y2SQB-STPBQ-H6PPB-WFGZ0
#30 4GPG5-TJGT4-Z11WX-8PWQP-JBM54
#31 K5Y7N-QD0K3-NV0M6-S70KD-MMD6D
#32 S0J7B-6MDXK-65VCV-BKVW1-XKF48
#33 DYGQK-YK1WP-ZKQNN-3C9L8-KD4DM
#34 5D6F1-G7VPC-F4H7F-K3H5M-8V9WR
#35 YQVX4-Z2YCF-W0607-0T6JF-Z3K0L
#36 6MHYP-50DQG-36NY4-T07GB-T8RM0
#37 C9W27-N2SJ3-8HB1P-4VD0F-R9QXL
#38 S0CXD-6MZ08-65X8Q-BKH6X-XK92H
#39 J5KC0-Q3HJP-GBWSC-5WXJV-YHT03
#40 JPRCN-QK7QP-G04G7-5GQF3-YZNFN
#41 C07RC-NGS0W-83G95-4444H-R15PZ
#42 4MJT3-3C192-HY369-MBJQH-N6H5Z
#43 LSVN2-2SYJC-LW6JM-QP617-7BK3F
#44 J100C-CBQQX-QVWBS-VTWPZ-03MZW
#45 T8PLF-XGTG8-WNSXX-L16VJ-GGKY5
#46 T9T3Y-X5YS9-WB04M-L9LHT-G0WTX
#47 J4VMP-Q79GS-GLY38-56JG5-YFHM1
#48 YG31S-BLSFJ-M8P0Y-BNPY4-X4GJV
#49 J45D0-C14BN-QXT9R-V977C-00R86
#50 JHXZ6-QF21M-GD189-5VCXK-Y9JBC
#51 KST2Q-QHL4T-NC8P2-SB868-M6Y2M
#52 4W3MS-G6ST5-7FPV6-YTPST-L3GKX
#53 SNWGZ-KC91N-Y445K-NY43R-VW5HJ
#54 Y8HWH-B310B-MXX2J-BQXLQ-XJTDB
#55 09H9B-1GDX6-HVNR3-6N73Q-44RHB
#56 6JRBR-59J85-34NP0-TJ216-TCS37
#57 S3B01-KP820-YZ72P-NC709-VDRXT
#58 L5VSF-21LLM-L3GJN-QXWGV-7PMM3
#59 5SFHJ-GHP1B-FCSCQ-KBCQB-86J50
#60 C7WG1-N9D6C-8DZ7F-40LJM-R8W0R
#61 JM04J-QSY3J-GX5GD-5M8Y7-YYYJF
#62 S7XLQ-K39TG-YQBNB-N3R5Y-VVVWP
#63 SV40X-KVSFL-YHWTY-NW9BK-VH4VC
#64 DY6YC-98HCK-Q1R61-F054N-H8CPY
#65 D7TXK-YGY0P-ZG08N-3FL68-KSW2M
#66 TWV4G-XV9VM-WPYKV-LHJ2G-G5H9S
#67 5GSBC-TLLMK-582F1-WNNCN-6481Y
#68 BRC6N-7SM63-3P5P6-725MD-BNCLD
#69 5QT9F-TSL88-5H8HX-WG8FJ-6ZYF5
#70 JSJ7J-C4D6B-QMVWQ-V0V7B-08F80
#71 KJ5V3-29HNQ-D4K4K-3JKN5-KCPS1
#72 BD6S1-77HL0-34RJP-735G9-BVCMT
#73 5DXDD-GW9BX-FDB9Z-KSR7L-8XV8K
#74 ZSDCJ-BHMBP-TCC3G-YBSMN-L61LY
#75 YKW9P-PLZKS-CV008-NH9S5-V54K1
#76 5BB3S-35M4J-PJZWY-7XKT4-BPPRV
#77 488XZ-TD88L-ZFV5B-8202S-JND9Q
#78 DXCG2-9KMDC-QC5XM-FR5F7-HQCFF
#79 J0M4B-CZTVK-QXDKV-VWZ21-0H698
#80 TWBL7-X6XGH-WFHX1-LTXV7-G3TYF
#81 Q99DN-VW5F2-2T64L-SY5PX-MWCZH
#82 ZZRHH-B8WRB-T7DVJ-YMDCQ-LYQ1B
#83 DV9BG-9H8MZ-QR1FL-FKMCS-HK21Q
#84 CJ0RQ-Y92LG-S4MBB-HJ6VY-WCKYP
#85 RWQ9X-66JML-0FG7Y-QTGRK-733CC
#86 CRKJ9-LS33V-1PJS5-5239S-YNZNQ
#87 C06Y5-LZHCF-1XR6F-5W541-YHCP8
#88 0PPLS-12TG5-HTSX6-666VT-4FKYX
#89 SR2MR-6FFG5-6YR30-BRRG6-XQVM7
#90 JDXYQ-Q4WYG-G9C7B-5NGVY-Y43YP
#91 40YL4-3M032-H505H-MK0J3-NKD0N
#92 JZ6K4-QZWG7-GQ3QK-58Z7J-YT685
#93 YKSL9-Z0WTV-WTLN5-0S05S-ZXDWQ
#94 57CL4-T3M32-5Q55H-W35J3-6VC0N
#95 CJ0PK-Y9251-S4MZD-HJ6BL-WCKVK
#96 C6G4K-LD1HP-11QTN-5V9R8-Y94CM
#97 LZSP2-287WC-L7BGM-QMBZ7-7YBQF
#98 YQ70R-PNLBY-C1SZQ-NJ7WT-VCR4X
#99 42LNF-GB358-71QSX-YFQQJ-LSN55

James


Duncan Smith wrote:[color=blue]
>
> Right, so you might be able to come up with something that produces similar
> output. Do you know if the strings are generated independently? If so,
> there must be some stochastic component (or unknown inputs) or the strings
> would be identical. How about the frequencies of the characters? Are some
> (significantly) more frequent than others? Do some characters follow others
> with unusually high frequency? Do characters tend to cluster (more or less
> that you'd expect from independently generated characters)? Unless the
> strings are very long you probably can't answer these questions too reliably
> with only 100 strings.
>
> Markov Chains are a possibility (as already mentioned). I'd probably start
> by looking at the simpler things first. The 1000 to 1200 sum might be a
> clue, particularly if you're having trouble emulating it. Of course, if
> this turns out to be some sort of code and you're looking at some encoded
> text, then that's something I know little about, and the above might be next
> to useless.
>
> Maybe the basic statistical tests in Gary Strangman's stats.py would be
> useful, unless you already have R and RPy?
>
> Duncan
>
>[/color]


--
-----------------------------------------------------------------------
James Sapara
Software Architect

Front Logic Inc. Tel: 306.653.2725 x14
Suite 300, Scotia Center Toll Free: 1.800.521.4510
111 Second Ave South Fax: 306.653.0972
Saskatoon, SK S7K 1K6
Canada
http://www.frontlogic.com james@frontlogi c.com

Find out what TYPENGO(tm) N300 Search Technology can do for your
company: http://www.frontlogic.com/interactiv...ngo/index.html
-----------------------------------------------------------------------

[James S]

Re: Python for Reverse Engineering

I got a few questions about the strings, so I figured I would share the
answers.

You wrote the algorithm that generated these strings?

Yes

How are the strings verified and proven to be legitimate?

There is a checksum encoded in the string that provides a basic check.
There is a unquice number encoded in each string that represents each
possible key.

There are 28629150 valid keys in the space of 28629150^5

Does the same algorithm that created them verify them?

The same string is feed back through the algo in reverse. Providing the
origional information that generated it.

James

James Sapara wrote:[color=blue]
> Well for the fun of it I'm gonna post 100 strings that are probably like
> the strings referred to earlier. I'll answer a limited set of questions
> about the keys if you want, but for the most part they are a set of 100
> unqiue keys, with two variable inputs and a few static inputs.
>[/color]

[James Sapara]

Re: Python for Reverse Engineering

Here's some statistical data from the set of keys I posted. I didn't do
any pattern matching, but I think this shows that the keys are fairly
random in composition. I have also included stats for a much larger set
of keys. I noticed in the set of 100 that I didn't get any keys in the
fourth deviation, so I wanted to make sure such keys do exist. If you
can think of any other stats from the ord values of character I could do
that as well. Since I know the algo I also know that the sets of 5 are
only for readability.

Pattern matching based on Number/Alpha would probably show that over a
large set of keys it matchs the ratio of numbers to alpha's used in the
keys. You could do binary comparisons of the N,A's and try to find
common patterns.

Min/Max ord values ('0', 48) ('Z', 90)
Min Sum/Max Sum/Average Sum 1200 2250 1725
Average value of byte 69
Number of Keys 100
Average sum of keys 1745
Range of Key Sums 1564 to 1894
STD range -3 to 3
Squard Root of Key Sums 79.1896457878

Min/Max ord values ('0', 48) ('Z', 90)
Min Sum/Max Sum/Average Sum 1200 2250 1725
Average value of byte 69
Number of Keys 10000
Average sum of keys 1753
Range of Key Sums 1460 to 1977
STD range -4 to 4
Squard Root of Key Sums 75.0266619276

James

****** wrote:
[color=blue]
> I'm not a cryptanalysis guy, is there any value in doing this to the
> strings, uploading this data to a DB and then searching for patterns:
>
> ;5V6XBTV6N65H7J 3WWTWQ6H74B;5V6 XB;TV6N6;5H7J3; WWTWQ;6H74B;NAN AAAANANNANANAAA AANANNA;NANAA;A ANAN;NANAN;AAAA A;NANNA;[53,
> 86, 54, 88, 66, 84, 86, 54, 78, 54, 53, 72, 55, 74, 51, 87, 87, 84,
> 87, 81, 54, 72, 55, 52, 66];[53, 86, 54, 88, 66];[84, 86, 54, 78,
> 54];[53, 72, 55, 74, 51];[87, 87, 84, 87, 81];[54, 72, 55, 52,
> 66];1733;347;356;3 05;426;299
> ;CBPPCLTJ5X1S8Z S5LVBZYRFVW;CBP PC;LTJ5X;1S8ZS; 5LVBZ;YRFVW;AAA AAAAANANANAANAA AAAAAAA;AAAAA;A AANA;NANAA;NAAA A;AAAAA;[67,
> 66, 80, 80, 67, 76, 84, 74, 53, 88, 49, 83, 56, 90, 83, 53, 76, 86,
> 66, 90, 89, 82, 70, 86, 87];[67, 66, 80, 80, 67];[76, 84, 74, 53,
> 88];[49, 83, 56, 90, 83];[53, 76, 86, 66, 90];[89, 82, 70, 86,
> 87];1881;360;375;3 61;371;414
> ;QJCT6VXYLT2S9Q ZSQ02GMJD9S;QJC T6;VXYLT;2S9QZ; SQ02G;MJD9S;AAA ANAAAAANANAAAAN AAAANA;AAAAN;AA AAA;NANAA;AANAA ;AANA;[81,
> 74, 67, 84, 54, 86, 88, 89, 76, 84, 50, 83, 57, 81, 90, 83, 81, 79,
> 50, 71, 77, 74, 68, 57, 83];[81, 74, 67, 84, 54];[86, 88, 89, 76,
> 84];[50, 83, 57, 81, 90];[83, 81, 79, 50, 71];[77, 74, 68, 57,
> 83];1867;360;423;3 61;364;359
>
>[/color]


--
-----------------------------------------------------------------------
James Sapara
Software Architect

Front Logic Inc. Tel: 306.653.2725 x14
Suite 300, Scotia Center Toll Free: 1.800.521.4510
111 Second Ave South Fax: 306.653.0972
Saskatoon, SK S7K 1K6
Canada
http://www.frontlogic.com james@frontlogi c.com

Find out what TYPENGO(tm) N300 Search Technology can do for your
company: http://www.frontlogic.com/interactiv...ngo/index.html
-----------------------------------------------------------------------

[Andrew Dalke]

Re: Python for Reverse Engineering

James S wrote:[color=blue]
> I got a few questions about the strings, so I figured I would share the
> answers.[/color]


I decided to play around with it for a bit.


The first digit of any group of 5 has less diversity. Here's a
histogram of the distinct number of characters for each position.

0 0456BCDJKLQRSTY Z
1 0123456789BDFGH JKLMNPQRSTVWXYZ
2 023456789BCDFGH JKLMPQRSTVWXY
3 012345679BCDFGH JKLMNPQRSTVWXYZ
4 012345679BCDFGH JKNPQRSTXYZ
5 1235679BCGKLNPQ TVXYZ
6 0123456789BCDFG HJKLMNPRSTVWXZ
7 0123456789CDFGH JKLMNPQSTVWXYZ
8 0123456789BCDFG HJKLMNPQRSTVWXY
9 0123456789BCFGH JKLMNPQRSTVWXYZ
10 01235678CDFGHKL MNPQSTWYZ
11 0123456789BCDFG HJKLMNPQRSTVWXY Z
12 0123456789BCDGH JKLMNPQRSTVWXYZ
13 0123456789BCDFG HJKLMNPQRSTVWXY Z
14 0123456789BCDFG HJKLMNPQRSTVWXY Z
15 0345678BDFHKLMN QSTVWY
16 0123456789BCDFG HJKLMNPQRSTVWXY
17 0123456789BCDGH JKLMNPQRSTVWXZ
18 012345679BCDFGH JKLMNPQRSTVWXYZ
19 0123456789BCDFG HJKLMNPQRSTVXYZ
20 046789BGHJKLMNR TVWXYZ
21 013456789BCDFGH JKLMNPQRSTVWXYZ
22 123456789BCDFGH JKLMNPQRSTVWYZ
23 0123456789BCDFH JKLMNPQRSTVWXYZ
24 012345678BCDFGH JKLMNPQRSTVWXYZ


There are 31 characters in the encoding. They are the
digits 0-9 and the consonants B-Z (including Y). I suspect
the vowels were omitted so no English words would be
generated by accident.

This gives a maximum space of 31**25 or
192327924899313 583338373139987 67870751
values.

Given
[color=blue]
> There are 28629150 valid keys in the space of 28629150^5[/color]

then that's
192327891309789 488910376259821 87500000
or smaller than 31**25 by
335895240944279 968801658037075 1

124 bits are needed to encode the full space because
[color=blue][color=green][color=darkred]
>>> 2**123 < 28629150**5 < 2**124[/color][/color][/color]
True[color=blue][color=green][color=darkred]
>>>[/color][/color][/color]

However it's also the case that
[color=blue][color=green][color=darkred]
>>> 2**123 < 31**25 < 2**124[/color][/color][/color]
True[color=blue][color=green][color=darkred]
>>>[/color][/color][/color]

This means at most a fraction of a bit (about 0.85)
is available for any checksum, since you say
[color=blue]
> There is a checksum encoded in the string that provides a basic check.
> There is a unquice number encoded in each string that represents each
> possible key.[/color]

If all possible keys in the space can be encoded by
this scheme then there's no extra space for a checksum.


I therefore don't know what that number means for this problem.

Supposing there is a checksum, it's probably the first digit
in the group. The loss of randomness is a clue -- the checksums
I know don't have that effect.


I can't tell if transpositions change the checksum. The only
anagram group is

#59 5SFHJ-GHP1B-FCSCQ-KBCQB-86J50
^^^^
#37 C9W27-N2SJ3-8HB1P-4VD0F-R9QXL
^^^^

and there may be a seed to the checksum which changes for
each group number, or the mapping from characters to numbers
can change based on the index in the string.

In any case, as others pointed out in this thread, if I really
had the code on my computer I would break out my disassembler
and start tracing code to reverse engineer it. Much easier
than trying to figure out the algorithm on these clues.


Andrew
dalke@dalkescie ntific.com

[Nick Craig-Wood]

Re: Python for Reverse Engineering

James S <james-newsgroups@echo blast.com> wrote:[color=blue]
> I got a few questions about the strings, so I figured I would share the
> answers.
>
> You wrote the algorithm that generated these strings?
>
> Yes
>
> How are the strings verified and proven to be legitimate?
>
> There is a checksum encoded in the string that provides a basic check.
> There is a unquice number encoded in each string that represents each
> possible key.
>
> There are 28629150 valid keys in the space of 28629150^5[/color]

ie about 24 bits of serial number in about 123 bits of key. If done
properly 123 bits of keys will ensure it isn't broken.
[color=blue]
> Does the same algorithm that created them verify them?
>
> The same string is feed back through the algo in reverse. Providing the
> origional information that generated it.[/color]

Here is my solution to the problem ;-) If your solution is anything
like this then it will never be broken! However if you keep the keys
to the algorithm in code you give to the user then it can be reverse
engineered of course.

$ python serial_key.py 314159265 141421356

Original serial 314159265
User Key is CRYX7T2FedtoJte oeeJx4MKiNvAgYS mKOB
Decoded serial number is 314159265
This is a valid key True

Original serial 141421356
User Key is CL33jINQiZo8xMq I0gnh3CCtutc1cX dfxH
Decoded serial number is 141421356
This is a valid key True


"""
Make a user key using md5

The secret keys must be kept secret, apart from that no harm in
publishing the algorithm

The user key is serial + md5(serial)

The serial numbers are fixed length strings and are encoded
unencrypted (but obfuscated) into the user key.

This is encoded into base 62 using str_to_long from ASCII to long then
long_to_str to get the long into base 62

This method is crypto secure IMHO (perhaps you'd better use SHA256 if
you are feeling really paranoid though!)

"""

import md5

SERIAL_LEN = 9
ASCII = "".join([chr(i) for i in range(256)])
KEYBASE = "ABCDEFGHIJKLMN OPQRSTUVWXYZabc defghijklmnopqr stuvwxyz0123456 789"
KEY1 = "secret key"
KEY2 = "another secret key"

def str_to_long(s, chars):
"Return a long representation of a string"
base = len(chars)
n = 0L
for c in s:
n *= base
n += chars.index(c)
return n

def long_to_str(n, chars):
"Return a string representation of a long"
base = len(chars)
s = []
while n:
n, c = divmod(n, base)
s.append(chars[c])
s.reverse()
return "".join(s)

def make_digest(ser ial):
"Makes a digest from a serial number and secret keys"
return md5.md5(KEY1 + serial + KEY2).digest()

def encode_key(seri al, digest):
"Encode the serial + digest in human readable form - returns a string"
assert len(serial) == SERIAL_LEN
return long_to_str(str _to_long(serial + digest, ASCII), KEYBASE)

def decode_key(key) :
"Returns a serial and digest decoded from a key"
decoded = long_to_str(str _to_long(key, KEYBASE), ASCII)
return decoded[:SERIAL_LEN], decoded[SERIAL_LEN:]

def check_digest(se rial, digest):
"Returns bool whether serial matches digest"
return make_digest(ser ial) == digest

if __name__ == "__main__":
import sys
if len(sys.argv) <= 1:
print "Put some serials on the command line"
for serial in sys.argv[1:]:
serial = serial.ljust(SE RIAL_LEN)[:SERIAL_LEN]
print
print "Original serial", serial
digest = make_digest(ser ial)
user_key = encode_key(seri al, digest)
print "User Key is ", user_key

# Now decode user_key to show how its done
decoded_serial, decoded_digest = decode_key(user _key)
print "Decoded serial number is", decoded_serial
print "This is a valid key", check_digest(de coded_serial, decoded_digest)



--
Nick Craig-Wood <nick@craig-wood.com> -- http://www.craig-wood.com/nick