I had a few reasons for starting this
competition:
· To give the newbies a chance to participate in a competition · To give old hands the chance to brush up on their assembly skills · To promote tight assembly coding
· To demonstrate the various different methods used to improve efficiency in coding

Well, I'm back from my short European jaunt and the competition is now closed. I have greatly enjoyed the entire competition, from the coding of the crackme and the chats with various crackers on IRC through to deciding the winner and writing this document.

Analysis of the Serial Scheme

The serial scheme was kept deliberately simple as it was written for newbies to train with. The scheme took a name of up to 16 bytes long and required a 16 byte serial number. There was a 256 byte lookup table that was indexed directly with the ASCII values of the name field. The name was padded to a length of 16 (if necessary) using values hardcoded into the scheme. The 256 byte lookup table was created using eight maximal 8 bit linear feedback shift registers (LFSRs) in parallel i.e. producing one output byte per 'clock'. The LFSRs were initialised to produce 'Ghir_OCU' as the first 8 output bytes. The table was precomputed and it was not expected that the cracker recognise the nature of the lookup table - although a post I made to the cracking forum about LFSRs might have tipped the more astute crackers!

The rules of the competition required that some standard interface text be included which strongly urged the use of service 9 interrupt 21h - though this would probably be used in any case - and discouraged blank screens and other unfriendly UIs from being used to save bytes. Also, the rules specified a range of input to be handled smaller than the possible 256 maximum. Due to the simple nature of the serial scheme, this meant that the lookup table could immediately be stripped down to the input range.

I envisioned that there would be 3 ‘fights’. One to reduce the original algorithm, second to reduce the packed table lookup algorithm and the last to reduce the LFSR algorithm. As it turned it, everyone seemed to go for the packed table option.

The Entrants

The following entrants have been included because they illustrate the different ideas and methods used to reach the common goal of reducing code size. I didn't realise that so many crackers would use the precomputed table method. Perhaps word got out during IRC chats and everybody started using them? In any case, this didn’t reduce the size cutting war as precomputation had its own routines that needed to be optimised.

Ghiribizzo Alpha (223 bytes)

This was not an entrant as it would hardly be fair for me to enter the competition knowing how the lookup table was generated! This keygen was basically converted from the crackme and improved 'on-the-fly' by generating the lookup table in code and tidying up routines where they were obviously inefficient. No great thought went into this and the code size was just to give myself an idea of what crackers would be aiming for. Aside from generating the lookup table, the only other unusual feature of this keygen was the use of the XLAT command instead of the standard indexing used in the crackme. I didn't stop to check whether this used less space or not, but included it as newbies may not be familiar with the XLAT instruction. As it happened, the XLAT instruction was used in Spyder’s keygen.

From the size I got from this keygen, I tried to guess a required key input range to put this size between thestraight table precomputation and the packed table precomputation.

One thing to note is how I ended the program. I was quite surprised by the fact that nobody else seemed to know that you could quit com programs with a ret instruction. Further size savings can be made by using Bb’s trick of keeping DH and also by tweaking the generator to fix some of the bitstreams produced to give us the bits we need and save later processing.

Cruehead Alpha (244 bytes)

I got this from Cruehead on IRC when I asked to see what he had managed so far. Although this version is unfinished it is still impressive. The keygen relies on precomputing the whole table and reducing the keygen to a single table lookup.

The coding is very simple - almost seems as if Cruehead was typing the steps going through his head straight onto the keyboard (perhaps he was?) the resulting code is consequently very easy to understand and follow.

Bb #10 (230 bytes)

Bb has written an excellent keygen. He has put some serious hard work into this including taking the time to calculate the dx offsets manually instead of just using the ‘offset’ feature that the compiler provides. It has been fun watching Bb’s keygen progress as the first one I received was version 5 which was 256 bytes long. The keygen presented here is version 10. There are other nice bits and bobs throughout this code. This makes it quite frustrating as in various places so much space is blatantly wasted. Just take a look at the last 6 lines of code! There shouldn’t even be 6 lines there! I’m sure Bb will learn a lot from seeing some of the other keygens here and I’m sure he will do very well should he enter the next competition.

Spyder (211 bytes)

Tidy, compact and elegantly coded. A little sparse in commenting (it seems like Spyder coerced IDA to write the keygen for him ;-p). The table lookup is an interesting piece of code.

VoidLord (247 bytes)

Another keygen using the idea of a packed precomputed table. VoidLord’s first keygen. Let’s hope we see more!

Honourable Mentions

Special mention given to Trykka who managed to deduce how the look-up table was created - but never sent in an entry!

The Winner

Well it looks like Spyder is the winner by quite a large margin. Incidentally, I have just made a quick check that the keygens work. You might be able to bump yourself up on the scale by picking holes in the other keygens :-)

Rankings

__Keygen______Size________Author______

    kgen.com    211         Spyder
kg.com      224         Ghiribizzo (alpha)
kg10.com    230         Bb
kg9.com     233         Bb
kg6.com     239         Bb
kgvoid.com  247         VoidLord
kgcrue.com  255         Cruehead (alpha)
kg5.com     256         Bb
kgt.com     529         Serial Scheme

Final Words

There have been some excellent ideas in the keygens. However, none of the keygens are as small as they could be. They all have some scope for improvement. By combining some of the ideas given in the above keygens, we could create a new smaller keygen. It will be interesting to see what the smallest possible keygen would look like.

I hope that everyone who has taken part in the competition, or who has followed it, has gained something from it. I hope that there will be more entries for the next competition!

The Source Codes

; Ghiribizzo’s Keygen ========================================================= .model tiny
.386
.code
.startup
; The first part of the code is the table generator ; Note that we can actually do some ‘precomputing’ by ; fixing some of the bits in the generator to produce ; the bits that we need. This will save some bytes ; in the serial section. I have not bothered to do this.

mov ax, 5547h
mov bx, 6869h
mov cx, 725fh
mov dx, 4f43h
mov di, offset PRD
mov si, offset PRD + 0ffh
LFSR:

stosb
;Save MSB
mov bp,ax
mov al,ah
and ax,0ffh
xchg ax,bp
;Tap
xor ah,bl
xor ah,ch
xor ah,al
;Shift
mov al,bh
mov bh,bl
mov bl,ch
mov ch,cl
mov cl,dh
mov dh,dl
;Store MSB
and dx,0ff00h
or dx,bp
cmp di,si
jle LFSR
;-----------------------------------------------------------------

mov ah,9
mov dx,offset startMsg
int 21h
mov ah,10
mov dx,offset NameInput
int 21h
;-----------------------------------------------------------------

mov si,offset NameBuffer
mov di,offset NameHash
mov bx,offset Table1
MakeSerial:

lodsb
xlat
and al,3fh
or al,30h
byteOK:

cmp al,39h
jle keepit
add al,7
keepit:

stosb
cmp di,offset stopbyte
jl MakeSerial
;-----------------------------------------------------------------

mov dx,offset NH2
printMsg:

mov ah,9
int 21h
exit:

ret

StartMsg    db      0dh,0ah,'OCU Keggen #1 ',0feh,' Ghiribizzo 1998 ',0dh,0ah
db      0dh,0ah,'Enter Name : $'
NameInput   db      17
NameRead    db      ?
NameBuffer  db      'mk3 "![]ns)%3x#0Z'
nh2         db      0dh,0ah,'Serial Number: '
NameHash    db      16 dup('y')
stopbyte    db      0dh,0ah,'$'

Table1:
PRD:
END

; Cruehead’s Keygen =========================================================== .model tiny
.386
.stack
.data

StartMsg    db      0dh,0ah,'OCU Keggen #1 ',0feh,' Cruehead 1998 ',0dh,0ah
db      0dh,0ah,'Enter Name : $'
SerialMsg   db      0dh,0ah,'Serial Number: '
NameVar     db      011h,0h,06Bh,06bh,033h,020h,022h,021h,05bh,05dh,06eh
db      073h,029h,025h,033h,078h,023h,030h,'$'
Table       db      037h,035h,034h,031h,036h,032h,046h,044h,046h,044h,044h
db      031h,035h,035h,038h,035h,036h,046h,032h,045h,036h,030h
db      031h,039h,033h,034h,030h,046h,031h,042h,044h,030h,043h
db      036h,043h,035h,039h,045h,039h,033h,036h,043h,037h,035h
db      036h,044h,045h,036h,032h,044h,031h,037h,039h,030h,031h
db      042h,046h,043h,034h,032h,031h,035h,037h,034h,044h,032h
db      032h,032h,030h,043h,034h,030h,044h,044h,033h,039h,044h
db      043h,038h,036h,031h,038h,041h,037h,034h,046h,045h,041h
db      036h,044h,043h,041h,041h,039h,043h,037h

.code
.startup

mov ah,09h
lea dx,StartMsg
int 21h
mov ah,0ah
lea dx,NameVar
int 21h
OnceAgain:

mov bl,NameVar[di+4]
cmp bl,0dh
jne noprob
mov bl,02bh
noprob:

mov al,table[bx-020h]
mov NameVar[di+2],al
inc di
cmp di,0Eh
jne OnceAgain
mov word ptr NameVar[16],00a0dh
mov ah,09h
lea dx,SerialMsg
int 21h
.exit
end

; Bb’s Keygen ================================================================= ; KG10 - Ghiribizzo KeyGen
; written by bb 12Sep98 1:30AM
; next revision 13Sep98 5:00PM
; yet more changes - 26Sep98 - late late night ; eat 3 more bytes 28Sep98
;
; comments where the evils lay
;
; I just knew that I HAD to make this thing 256 bytes of less. Beware: This ; is NOT an example of good coding practice! I almost wish I could do a ; "bytes saved" comparison for all the little hacks. ;
; I've gotten this to assemble under TASM. It MUST assemble as a 16-bit COM file, ; and even then I can't guarantee that the offsets will remain stable between ; various assemblers. Let me restate that: I CAN guarantee that this won't ; work for you when you try and assemble it yourself. :) ;
P8086
MODEL TINY
DATASEG

OffsetStartMsg      EQU     52h
OffsetMySerial      EQU     7fh
OffsetSerialMsg     EQU     91h
OffsetMyName        EQU     0a3h

StartMsg db 0dh,0ah,'OCU Keggen #1 ',0feh,' ----- bb ----- 1998',0dh,0ah ; There's no reason not to re-use this section of the StartMsg, since it fits ; perfectly though code had to be added to affix a linefeed MySerial db 0dh,0ah,'Enter Name : $' SerialMsg db 0dh,0ah,'Serial Number: $' ; previous change to MyName not needed anymore

MyName      db  11h, 0h, 6Dh, 6Bh, 33h, 20h, 22h, 21h, 5Bh, 5Dh, 6Eh, 73h, 29h,
db  25h, 33h, 78h, 23h, 30h, 5Ah

; Not only does the full table not need to be used, but since it's basically a ; substitution cypher we can fit everything into these 96 or so bytes ; Also, the trailing commented-out 37h saves us one byte. It's the substitution for 7Fh, ; but since 7Fh is a DELETE when using 0a/int21h, it never gets accepted by KGT.COM or by ; this keygen. Therefore, it's useless and unneeded. ; NewTable db '754162FDFDD155856F2E6019340F1BD0C6C59E936C756DE62D17901BFC421574 ; D2220C40DD39DC8618A74FEA6DCAA9C';, 37h ; and I missed the fact that it also only uses characters 0-9 and A-F ; which can be expressed in 4 bits, cutting the 96 byte table in half

NewTable    db      75h, 41h, 62h, 0FDh, 0FDh, 0D1h, 55h, 85h
db      6Fh, 2Eh, 60h, 19h, 34h, 0Fh, 1Bh, 0D0h
db      0C6h, 0C5h, 9Eh, 93h, 6Ch, 75h, 6Dh, 0E6h
db      2Dh, 17h, 90h, 1Bh, 0FCh, 42h, 15h, 74h
db      0D2h, 22h, 0Ch, 40h, 0DDh, 39h, 0DCh, 86h
db      18h, 0A7h, 4Fh, 0EAh, 6Dh, 0CAh, 0A9h, 0C7h

CODESEG
STARTUPCODE
; A note here: We're at