Another kept egg out of the dungeon
Dungeon Keeper, a strategy game from 1997, is filled with developer messages. While they can be read with a straightforward strings search in the executable, activating them is more fun. One of these messages, only present in the map editor (included in Dungeon Keeper Gold, released in 1998), was still missing an activation procedure:
In the following sections, I describe what was reversed in the executable to uncover such procedure. Funnily enough, getting the editor to run and debugging it was the trickier part!
Setup
As you can tell from the year 1998, this game sits in that virtualization gap where its too new (for DOSBox 1) and too old (for VirtualBox) to run decently in a version of Windows where a recent debugger can be used (x64dbg). I settled with Windows XP, which was able to run the game, but with some issues:
- CPU timing was way off, which made scrolling text unreadable, and any small movement of the mouse would send me from one edge of the map to the other;
- The game only ran fullscreen, with no option to run windowed, since the usual solutions didn’t seem to work (DxWnd, DxWrapper…). Luckily, alt-tabbing to the debugger was possible;
- Running the game from the debugger lead to runtime exceptions being thrown, so I had to first launch the game separately, then attach to it with the debugger, which could be an issue if some interesting subroutine was run before attaching 2;
- Hitting breakpoints caused the whole interface to freeze, even alt-tabbing didn’t render other windows… the only way out was to detach the debugger.
Breakpoints without breaks
To avoid freezes, the workaround was to set conditional breakpoints that did not stop the debugee (since the condition would always evaluate as false). The only action was logging the address at the instruction pointer when they were hit. Optionally, we could disable logging after the first hit, to reduce noise in the logs.
Translating this to the x64dbg scripting language (with an example address 00401234):
SetBPX 00401234
SetBreakpointCondition 00401234,0
SetBreakpointLog 00401234,hit:{eip}
SetBreakpointLogCondition 00401234,$breakpointcounter==1
Reasoning by analogy
So what kind of easter egg activations are we looking for?
For starters, we can decompile the map editor with Ghidra and check where the easter egg string is referenced, which leads to this subroutine:
void FUN_00415660(void) {
int iVar1;
uint uVar2;
if (DAT_006fd712 == '\0') {
DAT_006563d8 = '\0';
}
else {
if ((DAT_006563d8 == '\0') && (DAT_006fd716 != '\0')) {
FUN_00462440(0x9f);
DAT_006563d8 = '\x01';
}
if ((DAT_006563d8 == '\x01') && (DAT_006fd6fb != '\0')) {
FUN_00462440(0x9f);
DAT_006563d8 = '\x02';
}
if ((DAT_006563d8 == '\x02') && (DAT_006fd700 != '\0')) {
FUN_00462440(0x9f);
DAT_006563d8 = '\x03';
}
if ((DAT_006563d8 == '\x03') && (DAT_006fd6f9 != '\0')) {
FUN_00462440(0x9f);
DAT_006563d8 = '\x04';
}
}
if (DAT_006563d8 == '\x04') {
FUN_004673c0(0,0,(int)((ulonglong)DAT_004b73e0 / (ulonglong)(longlong)(int)(uint)DAT_004f7ebc),
(int)((ulonglong)DAT_004f7e94 / (ulonglong)(longlong)(int)(uint)DAT_004f7ebc));
DAT_006fd6b8._0_2_ = (ushort)DAT_006fd6b8 & 0xffbf;
DAT_004aa70c = DAT_004b7494;
FUN_0047bbd0(&DAT_004f8ec8,s_Hello_from_Mark_to_all_who_know_h_0048fd28);
// [...]
}
}
We can infer a state tracking variable (DAT_006563d8, or eastegg_mark_state), which is updated on each call to the function (FUN_00415660, or eastegg_mark), as long as some other checks were passed (DAT_006fd712, or eastegg_mark_check0; DAT_006fd716, or eastegg_mark_check1…). There’s a function call after each check passes (FUN_00462440), which seems to be related with sound (perhaps a specific sound at index 0x9f is played?):
void FUN_00462440(undefined4 param_1) {
int iVar1;
if ((DAT_0064d4f8 != 0) || (iVar1 = _GetCurrentSoundMasterVolume@0(), iVar1 < 1)) {
return;
}
if (DAT_006e73e4 != 0) {
iVar1 = FUN_004636f0(DAT_006e73e4);
if (iVar1 == 0) {
FUN_0043e110(s_D:\Dev\KeepNew\SOUND.cpp_0049c7d0,0xe9,
s_Non_3d_Emitter_has_been_deleted!_0049c7ec);
DAT_006e73e4 = 0;
}
if (DAT_006e73e4 != 0) {
FUN_004631f0(DAT_006e73e4,param_1,0,100,0x100,0,3,8,0x7ffffffe);
return;
}
}
DAT_006e73e4 = FUN_00463050(0,0,0,param_1,0,100,0x100,0,8,0x7ffffffe);
return;
}
At this point, it’s worth mentioning that we have the benefit of a partial source port existing, i.e. KeeperFX 3. Although it doesn’t include an editor, maybe some codepaths from the game’s main executable were shared with the editor executable. Indeed, the source port has an implementation that follows closely the previous sound subroutine:
void play_non_3d_sample(long sample_idx) {
if (SoundDisabled)
return;
if (GetCurrentSoundMasterVolume() <= 0)
return;
if (Non3DEmitter != 0)
if (!sound_emitter_in_use(Non3DEmitter)) {
ERRORLOG("Non 3d Emitter has been deleted!");
Non3DEmitter = 0;
}
if (Non3DEmitter == 0) {
Non3DEmitter = S3DCreateSoundEmitterPri(0, 0, 0, sample_idx, 0, 100, 256, 0, 8, 2147483646);
} else {
S3DAddSampleToEmitterPri(Non3DEmitter, sample_idx, 0, 100, 256, 0, 3, 8, 2147483646);
}
}
Now we can replace some names in our easter egg function:
void eastegg_mark(void) {
int iVar1;
uint uVar2;
if (eastegg_mark_check0 == '\0') {
eastegg_mark_state = '\0';
}
else {
if ((eastegg_mark_state == '\0') && (eastegg_mark_check1 != '\0')) {
play_non_3d_sample(0x9f);
eastegg_mark_state = '\x01';
}
if ((eastegg_mark_state == '\x01') && (eastegg_mark_check2 != '\0')) {
play_non_3d_sample(0x9f);
eastegg_mark_state = '\x02';
}
if ((eastegg_mark_state == '\x02') && (eastegg_mark_check3 != '\0')) {
play_non_3d_sample(0x9f);
eastegg_mark_state = '\x03';
}
if ((eastegg_mark_state == '\x03') && (eastegg_mark_check4 != '\0')) {
play_non_3d_sample(0x9f);
eastegg_mark_state = '\x04';
}
}
if (eastegg_mark_state == '\x04') {
FUN_004673c0(0,0,(int)((ulonglong)DAT_004b73e0 / (ulonglong)(longlong)(int)(uint)DAT_004f7ebc),
(int)((ulonglong)DAT_004f7e94 / (ulonglong)(longlong)(int)(uint)DAT_004f7ebc));
DAT_006fd6b8._0_2_ = (ushort)DAT_006fd6b8 & 0xffbf;
DAT_004aa70c = DAT_004b7494;
prepare_fmtstr(&prepared_str,s_Hello_from_Mark_to_all_who_know_h_0048fd28);
// [...]
}
}
Ok, but where are these variables set? Well… they aren’t? Following the cross-references to these check variables, 2 of them had a write reference, where they were only assigned with 0, and the other 2 had no write references. This required further investigation.
I turned to the main executable’s easter eggs, to better understand how they were activated. Let’s check the alex easter egg:
Start the game with the command line -alex, then while playing, hold down both Shift keys and type JLW. The sound of researching will play when each letter is pressed and a message will appear in the top left.
It also plays sounds like our easter egg. More precisely, it’s the same sound (at index 0x9f == 159), according to KeeperFX:
void input_eastegg(void) {
// [...]
// Maintain the JLW cheat
if ((game.flags_font & FFlg_AlexCheat) != 0) {
allow = (lbKeyOn[KC_LSHIFT]) && (lbKeyOn[KC_RSHIFT]);
state = input_eastegg_keycodes(&game.eastegg02_cntr,allow,&eastegg_jlw_codes);
if ((state == 1) || (state == 2) || (state == 3))
play_non_3d_sample(159);
}
// [...]
}
Were we missing a command line parameter?
Going back to our decompilation, by following references to our easter egg function, we see that it is called only when a given variable is set:
if (DAT_006563d4 != 0) {
FUN_00415660();
}
Which is written at this function:
undefined4 FUN_00456ce0(uint param_1,char **param_2) {
// [...]
pcVar3 = s_Dungeon_Keeper_Editor_0049b5d4;
// [...]
puVar11 = (undefined4 *)s_Bullfrog_Shell_004aa760;
// [...]
if (1 < param_1) {
// [...]
do {
cVar1 = **local_174;
if ((cVar1 != '-') && (cVar1 != '/')) { // parameter parsing?
LAB_00456f75:
// [...]
}
iVar4 = FUN_004873b0(s_level_0049b5cc,local_164);
if (iVar4 == 0) {
local_174 = local_174 + 1;
local_17c = local_17c + 1;
iVar7 = iVar7 + 1;
local_180 = local_180 + 1;
iVar8 = iVar8 + 1;
local_178 = local_178 + 1;
local_168 = FUN_0047bda0(&local_144);
DAT_004f92dc = DAT_004f92dc | 2;
}
else {
iVar4 = FUN_004873b0(s_noerrors_0049b5c0,local_164);
if (iVar4 == 0) {
DAT_004f92e1 = DAT_004f92e1 | 0x20;
}
else {
iVar4 = FUN_004873b0(&DAT_0049b5b8,local_164); // unidentified string?
if (iVar4 != 0) goto LAB_00456f75;
DAT_006563d4 = 1; // is_eastegg_mark_set = 1
}
}
}}}
Which in turn, is called at the end of:
undefined4 FUN_00466c20(undefined4 param_1) {
char cVar1;
LPSTR _Source;
char *pcVar2;
char *pcVar3;
size_t _Count;
_Count = 0x103;
DAT_006fd23c = param_1;
_Source = GetCommandLineA();
pcVar2 = _strncpy(&DAT_006fd138,_Source,_Count);
pcVar3 = &DAT_006fd138;
DAT_006fd240 = 0;
while (*pcVar3 != '\0') {
while( true ) {
pcVar2 = (char *)((uint)pcVar2 & 0xffffff00);
if ((*pcVar3 != '\t') && (*pcVar3 != ' ')) break;
pcVar3 = pcVar3 + 1;
}
// [...]
}
// parse command line
FUN_00456ce0((uint)pcVar2 & 0xffff0000 | (uint)DAT_006fd240,&DAT_006fd248);
if ((DAT_004aa75c != (code **)0x0) &&
((**(code **)(*DAT_004aa75c + 0x30))(), DAT_004aa75c != (code **)0x0)) {
(**(code **)*DAT_004aa75c)(1);
}
return 0;
}
The first strings (s_Dungeon_Keeper_Editor_0049b5d4, s_Bullfrog_Shell_004aa760), according to KeeperFX, are related with the graphical window setup, so we are somewhere early in the program lifecycle. We see that FUN_00466c20 reads the command line (GetCommandLineA()) and passes it to FUN_00456ce0, which seems to be parsing parameters. For the is_eastegg_mark_set check, the compared string wasn’t identified, due to it having a length of 4 (by default, Ghidra searches for strings with a minimum length of 5), but you can tell where this is going:
DAT_0049b5b8 XREF[1]: FUN_00456ce0:00456f1e(*)
?? 6Dh m
?? 61h a
?? 72h r
?? 6Bh k
?? 00h
After putting a breakpoint on the DAT_006563d4 check, and running the editor with this parameter (on x64dbg: Menu > File > Change Command Line > "C:\Program Files\Bullfrog\Keeper\Editor.exe" -mark), we get a hit. So that’s one part of the puzzle.
Back to the state checks. To be sure we weren’t missing any writes to these addresses, we could place write-only hardware breakpoints, following the non-stopping approach described earlier:
// clear previous breakpoints
bc
bphwc
bpmc
// check 0
bphws 006fd712,w,1
SetHardwareBreakpointCondition 006fd712,0
SetHardwareBreakpointLog 006fd712,hit_0:{eip}_v:{byte(006fd712)}
// check 1
bphws 006fd716,w,1
SetHardwareBreakpointCondition 006fd716,0
SetHardwareBreakpointLog 006fd716,hit_1:{eip}_v:{byte(006fd716)}
// check 2
bphws 006fd6fb,w,1
SetHardwareBreakpointCondition 006fd6fb,0
SetHardwareBreakpointLog 006fd6fb,hit_2:{eip}_v:{byte(006fd6fb)}
// check 3
bphws 006fd700,w,1
SetHardwareBreakpointCondition 006fd700,0
SetHardwareBreakpointLog 006fd700,hit_3:{eip}_v:{byte(006fd700)}
// check 4
bphws 006fd6f9,w,1
SetHardwareBreakpointCondition 006fd6f9,0
SetHardwareBreakpointLog 006fd6f9,hit_4:{eip}_v:{byte(006fd6f9)}
// all checks passed at this point
SetBPX 00415731
So now it was a matter of attaching the debugger, going back to the editor, then enumerating key presses, checking if anything was logged. After a few iterations:
// left_shift
hit_0:46C461_v:1
// left_shift + c
hit_1:46C461_v:1
hit_1:46C4CA_v:11
hit_1:46C44A_v:0
// c
hit_1:46C461_v:1
hit_1:46C4CA_v:1
hit_1:46C44A_v:0
// r
hit_2:46C461_v:1
hit_2:46C4CA_v:1
hit_2:4150EC_v:0
hit_2:46C44A_v:0
// o
hit_3:46C461_v:1
hit_3:46C4CA_v:1
hit_3:414EF0_v:0
hit_3:46C44A_v:0
// w
hit_4:46C461_v:1
hit_4:46C4CA_v:1
hit_4:46C44A_v:0
Neat! So the addresses are actually set with indirect writes, under function FUN_0046c360, which has an elaborate switch-case statement4 that parses the scan code of the pressed key:
undefined4 FUN_0046c360(undefined4 param_1,undefined4 param_2,uint param_3) {
byte *pbVar1;
uint uVar2;
// Get scan code byte from `param_3`, store in `uVar2`
uVar2 = (int)param_3 >> 0x10;
DAT_006fd6e0 = '\x01' - ((param_3 & 0x1000000) == 0);
if (DAT_006fd6e0 != '\0') {
uVar2 = (uint)(byte)((char)(param_3 >> 0x10) + 0x80);
}
uVar2 = uVar2 & 0xff;
if (uVar2 == 0x2b) {
uVar2 = 0x56;
}
else {
if (true) {
switch(DAT_004aa708) {
case 2:
if (true) {
switch(uVar2) {
case 0x10:
uVar2 = 0x1e;
break;
case 0x11:
uVar2 = 0x2c;
break;
case 0x1e:
uVar2 = 0x10;
break;
case 0x27:
uVar2 = 0x32;
break;
case 0x2c:
uVar2 = 0x11;
break;
case 0x32:
uVar2 = 0x33;
break;
case 0x33:
uVar2 = 0x27;
}
}
break;
case 3:
if (uVar2 == 0x15) {
uVar2 = 0x2c;
}
else {
if (uVar2 == 0x2c) {
uVar2 = 0x15;
}
}
break;
case 7:
if (uVar2 == 0x15) {
uVar2 = 0x2c;
}
else {
if (uVar2 == 0x2c) {
uVar2 = 0x15;
}
}
}
}
}
// Indirect writes to our check variables
if ((param_3 & 0x80000000) == 0) {
(&DAT_006fd6e8)[uVar2] = 1;
DAT_006fd6e4 = (byte)uVar2;
}
else {
(&DAT_006fd6e8)[uVar2] = 0;
DAT_006fd6e0 = '\0';
}
// [...]
}
A closer look at these writes:
0046c432 f7 c6 00 TEST ESI,0x80000000
00 00 80
0046c438 88 54 24 07 MOV byte ptr [ESP + local_1],DL ; uVar2
0046c43c 74 15 JZ LAB_0046c453
; [...]
0046c453 33 c0 XOR EAX,EAX
0046c455 8a 44 24 07 MOV AL,byte ptr [ESP + local_1]
0046c459 05 e8 d6 ADD EAX,DAT_006fd6e8
6f 00
0046c45e c6 00 01 MOV byte ptr [EAX],offset DAT_006fd6e8 ; (&DAT_006fd6e8)[uVar2] = 1;
We can verify the scan code values by taking the address and result register after processing the scan code:
FUN_0046c360
0046c360 83 ec 04 SUB ESP,0x4
0046c363 56 PUSH ESI
0046c364 8b 74 24 14 MOV ESI,dword ptr [ESP + param_3]
0046c368 8b ce MOV ECX,ESI
0046c36a 8b c6 MOV EAX,ESI
0046c36c c1 f9 10 SAR ECX,0x10
; [...]
0046c389 80 c1 80 ADD CL,0x80
LAB_0046c38c
0046c38c 33 d2 XOR EDX,EDX
0046c38e 8a d1 MOV DL,CL ; At this point, CL contains the scan code byte value
Then adding this breakpoint:
SetBPX 0046c38e
SetBreakpointCondition 0046c38e,0
SetBreakpointLog 0046c38e,hit:{eip}_key:{ecx}
Which logs:
// left_shift
hit:46C38E_key:2A
hit:46C38E_key:FFFFC02A
// q
hit:46C38E_key:10
hit:46C38E_key:FFFFC010
// w
hit:46C38E_key:11
hit:46C38E_key:FFFFC011
// e
hit:46C38E_key:12
hit:46C38E_key:FFFFC012
// [...]
Now, to understand this condition:
(param_3 & 0x80000000) == 0
Let’s try logging before processing param_3, at address 0046c36a:
// left_shift
hit:46C36A_key:002A0001
hit:46C36A_key:C02A0001
// q
hit:46C36A_key:00100001
hit:46C36A_key:C0100001
// left_shift + q
hit:46C36A_key:402A0001
For each key, first value is the key pressed down, second value is the key released. The condition just checks if it was pressed down, then sets the corresponding relative address of the key variable, otherwise clears it. So our check variables are just references to some of these keys. This indirection explains why the write cross-references weren’t identified by Ghidra.
Show us the easter egg already!
Here it is, on a PCem setup that offers better accuracy, Mark’s message:
TL;DR
- Run the editor with parameter
-mark; - Hold down left shift, then type
CROW5.
-
Maybe one of those forks which support installing Windows 95/98 could work here, but I didn’t explore that option. ↩
-
If needed, we could always patch in some infinite loop to hang the executable around some address (e.g. bytes
\xEB\xFErepresent a jump with offset zero), later on manually applying in the debugger script whatever instructions we replaced. ↩ -
After the fact, I realized that KeeperFX’s source code had a mappings file under
./lib/keeper95_gold.map. If adapted into a format compatible with Ghidra’s FID database, they would have helped a lot in identifying functions. ↩ -
Maybe hacks to support multiple keyboard layouts, which would have some keys in different positions. ↩
-
Initially I had
QCROW, but check 0 only requires left shift to be pressed down, making any additional key redundant. Thanks AdamP for pointing this out. ↩