FCSC 2023: Virtual Machine

The virtual machine described on this page covers the following five challenges:

• Comparaison intro
• Fibonacci hardware
• RSA Secure Dev (1/3) fault attacks
• RSA Secure Dev (2/3) fault attacks
• RSA Secure Dev (3/3) fault attacks

These five challenges share two files:

• machine.py: the Python file evaluating this machine instructions.
• assembly.py: an assembler described below.

Assembler

A rough assembler written in Python is provided (assembly.py) to generate the bytecode that will be interpreted. This assembler supports label recognition (string of letters terminated by :) to facilitate code jumps. The comment character is ;.

Virtual machine description

The machine contains 16 registers that can hold numbers as large as required. Registers are numbered from 0 to F. A hexadecimal system is used to designate the registers (e.g. RA instead of R10).

On initialization, the machine expects to receive:

1. initial values in its input registers. The input registers are R5 to RC.
2. a sequence of instructions which will be the code interpreted by the machine. This sequence is divided into 16-bit words in an array, with the first word at index 0 of the array.

For RSA Secure Dev challenges, with no guarantee of integrity:

1. a message will be placed in register R5.
2. a prime number p will be placed in register R6.
3. a prime number q will be placed in register R7.
4. a number iq will be placed in register R8 (iq = q**(-1) mod p).
5. a number dp will be placed in register R9 (dp = e**(-1) mod (p-1)).
6. a number dq will be placed in register RA (dq = e**(-1) mod (q-1)).
7. a number e will be placed in register RB.
8. a number d will be placed in register RC (d = e**(-1) mod (p-1)(q-1)).

Virtual machine execution

The virtual machine interprets the sequence, starting with the first 16-bit word at address 0 in the sequence.

The virtual machine always sets the program counter (PC) to the next instruction after loading and decoding an instruction. After loading, the instruction is executed, updating the machine’s register values.

Instructions list

Summary table

Family	Operation	Assembler	Updates	Action	Error
Move	Move	MOV Rj, op2	-	Rj = op2
Load	Move from code (1 word)	MOVCW Rj	-	Rj = @Rj
	Move from code (Ri words)	MOVC Rj, Ri	-	Rj = @Rj
Logical	AND	AND Ro, Rm, Rn	-	Ro = Rm & Rn
	OR	OR Ro, Rm, Rn	-	Ro = Rm | Rn
	XOR	XOR Ro, Rm, Rn	-	Ro = Rm ^ Rn
	Shift right	SRL Ro, Rm, Rn	-	Ro = Rm >> Rn
	Shift left	SLL Ro, Rm, Rn	-	Ro = Rm << Rn
Arithmetic	Bit length	BTL Rj, Ri	-	Rj = bit_length(Ri)
	Add	ADD Ro, Rm, Rn	-	Ro = Rm + Rn
	Subtract	SUB Ro, Rm, Rn	Z C	Ro = Rm - Rn
	Comparison	CMP Rj, Ri	Z C	Rj - Ri
	Multiplication	MUL Ro, Rm, Rn	Z	Ro = Rm * Rn
	Division	DIV Ro, Rm, Rn	-	Ro = Rm // Rn	Rn=0
	GCD	GCD Ro, Rm, Rn	-	Ro = gcd(Rm,Rn)
Modular	Modular reduction	MOD Rj, Ri	-	Rj = Ri mod RD	RD=0
	Modular exponentiation	POW Rj, Ri	-	Rj = Ri**RC mod RD	RD=0
	Modular inversion	INV Rj, Ri	-	Rj = Ri**(-1) mod RD	RD=0
Random	Random	RND Rj	-	Rj = rand < 2**(8*Rj)	Rj=0
Branch (Absolute)	Jump if Z set	JZA adest	-	PC = adest if Z=True	PC>=l or PC < 0
	Jump if Z not set	JNZA adest	-	PC = adest if Z=False	PC>=l or PC < 0
	Jump if C set	JCA adest	-	PC = adest if C=True	PC>=l or PC < 0
	Jump if C not set	JNCA adest	-	PC = adest if C=False	PC>=l or PC < 0
	Jump	JA adest	-	PC = adest	PC>=l or PC < 0
Branch (Relative)	Jump if Z set	JZR rdest	-	PC += rdest if Z=True	PC>=l or PC < 0
	Jump if Z not set	JNZR rdest	-	PC += rdest if Z=False	PC>=l or PC < 0
	Jump if C set	JCR rdest	-	PC += rdest if C=True	PC>=l or PC < 0
	Jump if C not set	JNCR rdest	-	PC += rdest if C=False	PC>=l or PC < 0
	Jump	JR rdest	-	PC += rdest	PC>=l or PC < 0
Call (Absolute)	Call	CA adest	-	LR = PC, PC = dest	PC>=l or PC < 0
Call (Relative)	Call	CR adest	-	LR = PC, PC += dest	PC>=l or PC < 0
Return	Return	RET	-	PC = LR	PC>=l or PC < 0
End	Stop	STP	-
Tabular	allocate constants	.word cst, ...	-

 

Notations :

• Ri = R[0-9A-F]
• Rj = R[0-9A-F]
• Rm = R[0-7]
• Rn = R[0-7]
• Ro = R[0-7]
• op2 = Ri, #[0-9]+, #0x[0-9a-fA-F]+, =[a-zA-Z]\w+
• rdest = Ri, [a-zA-Z]\w+, \+[0-9]+, -[0-9]+
• adest = Ri, [a-zA-Z]\w+, #[0-9]+, #0x[0-9a-fA-F]+
• cst = [0-9]+, 0x[0-9a-fA-F]+
• l designates the number of words (16 bits) in the code

After a # the number must be able to be represented on 16 bits. After a + the number must be able to be represented on 7 bits. After a -, the number x must respect: 0 < x <= 128 If rdest = Ri, then the 8th bit is signed (-128 instead of 128).

Special registers:

• RC is used as exponent
• RD is used as modulo
• RE is used as Link Register
• RF is used as Program Counter

Instruction détails

MOV Rj, op2

Rj = op2

MOV Rj, =label

Rj = label

AND Ro, Rm, Rn

Ro = Rm & Rn

OR Ro, Rm, Rn

Ro = Rm | Rn

XOR Ro, Rm, Rn

Ro = Rm ^ Rn

SRL Ro, Rm, Rn

Ro = Rm >> Rn

SLL Ro, Rm, Rn

Ro = Rm << Rn

BTL Rj, Ri

Rj = bit_len(Ri)

ADD Ro, Rm, Rn

Ro = Rm + Rn

SUB Ro, Rm, Rn

Ro = Rm - Rn

Updates two Booleans Z and C:

• Z = True if Rm == Rn, else Z = False
• C = False if Rm< Rn, else C = True

MUL Ro, Rm, Rn

Ro = Rm*Rn

Updates one Boolean Z:

• Z = True if Rm == 0 ou Rn == 0, else Z = False

DIV Ro, Rm, Rn

Ro = Rm//Rn = quotient(Rm,Rn)

If Rn == 0, an error will be raised (and program will stop).

MOD Rj, Ri

Rj = Ri mod module

If module == 0, an error will be raised (and program will stop).

POW Rj, Ri

Rj = Ri**exponent mod modulo

If module == 0, an error will be raised (and program will stop).

GCD Ro, Rm, Rn

Ro = gcd(Rm,Rn)

INV Rj, Ri

Rj = Ri**(-1) mod module

If module == 0, an error will be raised (and program will stop).

RND Rj

Rj = random of Rj bytes

If Rj == 0, an error will be raised (and program will stop).

CMP Rj, Ri

Updates 2 Booleans Z and C :

• Z = True if Rj == Ri, else Z = False
• C = False if Rj< Ri, else C = True

MOVCW Rj

Rj = @Rj

Read 1 word (2 bytes) from address Rj. The word at address Rj is the most significant word of the considered value.

MOVC Rj, Ri

Rj = @Rj

Ri indicates the amount of words to read from address Rj. The word at address Rj is the most significant word of the considered value.

JZA adest

PC = adest if Z = True

If PC overflow code size or is negative, an error will be raised (and program will stop).

JNZA adest

PC = adest if Z = False

If PC overflow code size or is negative, an error will be raised (and program will stop).

JZR rdest

PC += rdest if Z = True

If PC overflow code size or is negative, an error will be raised (and program will stop).

JNZR rdest

PC += rdest if Z = False

If PC overflow code size or is negative, an error will be raised (and program will stop).

JCA adest

PC = adest if C = True

If PC overflow code size or is negative, an error will be raised (and program will stop).

JNCA adest

PC = adest if C = False

If PC overflow code size or is negative, an error will be raised (and program will stop).

JCR rdest

PC += rdest if C = True

If PC overflow code size or is negative, an error will be raised (and program will stop).

JNCR rdest

PC += rdest if C = False

If PC overflow code size or is negative, an error will be raised (and program will stop).

JA adest

PC = adest

If PC overflow code size or is negative, an error will be raised (and program will stop).

JR rdest

PC += rdest

If PC overflow code size or is negative, an error will be raised (and program will stop).

CA adest

LR = return address (PC)
PC = adest

If PC overflow code size or is negative, an error will be raised (and program will stop).

CR rdest

LR = return address (PC)
PC += rdest

If PC overflow code size or is negative, an error will be raised (and program will stop).

RET

PC = LR

If PC overflow code size or is negative, an error will be raised (and program will stop).

STP

Program end