Password Algorithms: Windows System Key (SYSKEY)

I stumbled upon some forum posts related to System Key recently and read something about 1 of the authentication modes available to Administrators that made me wonder if true or not.

Just to note, there are 3 modes.

1. Generated by passphrase
2. Stored in registry
3. Stored on removable storage device

2 is enabled by default, but you can change this with the syskey.exe utility.

The claim was that if you forgot the passphrase or “startup password” there’s no reliable method of recovery. The “only way” to get back into the system is to restore a backup if one is available or disable completely using something like ntpasswd

In most cases, either way is probably sufficient enough, but there are situations where you would need to know the original passphrase and don’t have a backup available or perhaps you can’t even use a backup which could erase some critical information required.

There are a number of ways to recover the passphrase but I’ll just suggest one for now.
Found this short video which shows someone enabling the startup password

One of the the comments is “BOSS HOW WE HACK SYSKEY!!!” 

History of SYSKEY

SYSKEY was Microsoft’s response to pwdump and L0phtCrack.
It was provided as an optional security enhancement with Windows NT SP3 and enabled by default since the release of Windows 2000.

The purpose of this feature was to prevent pwdump working without modifications. Open source offline decryption tools didn’t surface until the release of samdump2 by Nicola Cuomo.

What follows is a short timeline of events related to SYSKEY.

March 1997	Samba developer Jeremy Allison publishes pwdump which enables Administrators to dump LM and NTLM hashes stored in the SAM database.
April 1997	L0pht publishes L0phtcrack which allows Administrators to audit password hashes. It had been in development since the release of pwdump.
May 1997	Microsoft publishes Service Pack 3 for Windows NT which added SYSKEY as an optional feature to prevent pwdump working properly.
December 1999	Todd Sabin documents flaw with SYSKEY. Anyone with access to the SAM database can reveal password hashes without the System key.
April 2000	Todd Sabin releases pwdump2 which dumps password hashes with the obfuscation removed. This also dumps hashes from a domain controller.
February 2004	Nicola Cuomo documents SYSKEY, Releases Samdump2 which enables offline decryption of password hashes stored in SAM database.

Password Generation

When the system boots and auth mode 1 is enabled, windows will display a dialog box waiting for you to enter the password. The following text is displayed on an XP system.

“This computer is configured to require a password in order to start up. Please enter the Startup Password below.”

Blank passwords are acceptable so whether you enter something or not, it gets processed with MD5 and authenticated once you hit OK.

#define MAX_SYSKEY_PWD 260

void pwd2key(wchar_t pwd[], uint8_t syskey[]) {
  MD5_CTX ctx;
  size_t pwd_len = wcslen(pwd);
  pwd_len = (pwd_len > MAX_SYSKEY_PWD) ? MAX_SYSKEY_PWD : pwd_len;
 
  MD5_Init(&ctx);
  MD5_Update(&ctx, pwd, pwd_len);
  MD5_Final(syskey, &ctx);
}

Enter the wrong password 3 times and you’ll receive the following error.

“System error: Lsass.exe”
“When trying to update a password the return status indicates that the value provided as the current password is not correct.”

This message appears because the LSA database key fails to decrypt but I wanted to know how exactly this password was authenticated.

Between XP and Vista, the LSA database got a major upgrade so you may see something else on post-XP systems.

If you were to attempt recovery through the LSA database, it would not only be much slower, it’s more complicated and because there’s a simpler way, I’m not going to cover it.

SAM Database

The SAM database is stored in %SystemRoot%\System32\config\SAM which as you probably know contains local user and group information, including encrypted NTLM/LM hashes.

Windows reads the value of F under SAM\Domains\Account and using the System key, decrypts the Sam key.

The structure of the F value isn’t documented but I’ve put together what I *think* is close enough to the original based on some MSDN documentation and analyzing code inSAMSRV.DLL which is where the decryption occurs.

#define SYSTEM_KEY_LEN   16
 
#define QWERTY "!@#$%^&*()qwertyUIOPAzxcvbnmQQQQQQQQQQQQ)(*@&%"
#define DIGITS "0123456789012345678901234567890123456789"

#define SAM_KEY_LEN      16
#define SAM_SALT_LEN     16
#define SAM_CHECKSUM_LEN 16

typedef struct _SAM_KEY_DATA {
  uint32_t Revision;
  uint32_t Length;
  uint8_t Salt[SAM_SALT_LEN];
  uint8_t Key[SAM_KEY_LEN];
  uint8_t CheckSum[SAM_CHECKSUM_LEN];
  uint32_t Reserved[2];
} SAM_KEY_DATA, *PSAM_KEY_DATA;

typedef enum _DOMAIN_SERVER_ENABLE_STATE {
  DomainServerEnabled = 1,
  DomainServerDisabled
} DOMAIN_SERVER_ENABLE_STATE, *PDOMAIN_SERVER_ENABLE_STATE;

typedef enum _DOMAIN_SERVER_ROLE {
  DomainServerRoleBackup  = 2,
  DomainServerRolePrimary = 3
} DOMAIN_SERVER_ROLE, *PDOMAIN_SERVER_ROLE;

typedef struct _OLD_LARGE_INTEGER {
  unsigned long LowPart;
  long HighPart;
} OLD_LARGE_INTEGER, *POLD_LARGE_INTEGER;

#pragma pack(4)
typedef struct _DOMAIN_ACCOUNT_F {
  uint32_t Revision;
  uint32_t unknown1;
  
  OLD_LARGE_INTEGER CreationTime;
  OLD_LARGE_INTEGER DomainModifiedCount;
  OLD_LARGE_INTEGER MaxPasswordAge;
  OLD_LARGE_INTEGER MinPasswordAge;
  OLD_LARGE_INTEGER ForceLogoff;
  OLD_LARGE_INTEGER LockoutDuration;
  OLD_LARGE_INTEGER LockoutObservationWindow;
  OLD_LARGE_INTEGER ModifiedCountAtLastPromotion;
  
  uint32_t NextRid;
  uint32_t PasswordProperties;
  uint16_t MinPasswordLength;
  uint16_t PasswordHistoryLength;
  uint16_t LockoutThreshold;
  uint16_t unknown2;
  
  DOMAIN_SERVER_ENABLE_STATE ServerState;
  DOMAIN_SERVER_ROLE ServerRole;
  
  uint8_t UasCompatibilityRequired;
  uint32_t unknown3[2]; 
  
  SAM_KEY_DATA keys[2];
  uint32_t unknown4;
} DOMAIN_ACCOUNT_F, *PDOMAIN_ACCOUNT_F;
#pragma pack()

NTSTATUS DecryptSamKey(PSAM_KEY_DATA key_data, uint8_t syskey[]) {
  MD5_CTX ctx;
  RC4_KEY key;
  uint8_t dgst[MD5_DIGEST_LEN];
  
  // create key with salt and decrypt data
  MD5_Init(&ctx);
  MD5_Update(&ctx, key_data->Salt, SAM_SALT_LEN);
  MD5_Update(&ctx, QWERTY, strlen(QWERTY) + 1);
  MD5_Update(&ctx, syskey, SYSTEM_KEY_LEN);
  MD5_Update(&ctx, DIGITS, strlen(DIGITS) + 1);
  MD5_Final(dgst, &ctx);
  
  RC4_set_key(&key, MD5_DIGEST_LEN, dgst);
  RC4(&key, SAM_CHECKSUM_LEN + SAM_KEY_LEN, 
      key_data->Key, key_data->Key);
  
  // verify decryption was successful by generating checksum
  MD5_Init(&ctx);
  MD5_Update(&ctx, key_data->Key, SAM_KEY_LEN);
  MD5_Update(&ctx, DIGITS, strlen(DIGITS) + 1);
  MD5_Update(&ctx, key_data->Key, SAM_KEY_LEN);
  MD5_Update(&ctx, QWERTY, strlen(QWERTY) + 1);
  MD5_Final(dgst, &ctx);
  
  // compare with checksum and return status
  if (memcmp(dgst, key_data->CheckSum, SAM_CHECKSUM_LEN) == 0) {
    return STATUS_SUCCESS;
  }
  return STATUS_WRONG_PASSWORD;
}

NOTE: The strings didn’t format well for the blog but if you plan on using, let me know.

As you can see above, the Sam key is decrypted using System key and then a checksum is generated and compared with that stored in SAM_KEY_DATA
If they match, authentication succeeded, return STATUS_SUCCESS elseSTATUS_WRONG_PASSWORD

That’s pretty much how you can brute force the System Key when auth mode 1 is selected.

Recovery

Assuming you can read the F value from SAM hive, recovery is straight forward enough with the right libraries/code.

Following is just some pseudo code to demonstrate flow of recovery using dictionary attack.

    sam = openfile("offline_system\Windows\config\SAM");
   data = readreg(sam, "SAM\Domains\Account", "F")
 
  words = openfile("dictionary.txt")
 
  while (readfile(words, pwd)) {
    pwd2key(pwd, syskey)
    if (DecryptSamKey(data->keys[0], syskey) == STATUS_SUCCESS) {
      print "Found password: " + pwd
      break;
    }
  }
  closefile(words)
  closefile(sam)

LSA and NTDS algorithms call a hash function 1000 times during creation
of the encryption/decryption key while SAM algorithm doesn’t use any.

It’s not a vulnerability but could be useful to know some day.