FCSC 2025: Virtual machine

Table of contents

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

Poète intro
Milles Fautes intro
Il etait une bergere misc
Atomic Secable fault attacks
No Divide Just Conquer (1/3) fault attacks
No Divide Just Conquer (2/3) fault attacks
No Divide Just Conquer (3/3) fault attacks

These seven challenges share three files:

machine.py : le fichier Python évaluant les instructions de cette machine.
assembly.py : un assembleur décrit plus bas.
crypto_accelerator.py : le fichier contient une implémentation d’arithmétique modulaire de Montgomery.

The “Mille Fautes” introductory challenge and the “Atomic Secable” challenge also use the following file:

machine_faulted.py : le fichier contient une classe fille de la machine pour simuler des fautes (écriture d’une valeur aléatoire dans le registre de destination).

The “No Divide Just Conquer” challenges series also uses the following two files:

machine_restricted.py : le fichier contient des classes filles de la machine afin de restreindre les opérations supportées.
no-divide-just-conquer.py : le fichier principal de la série de trois épreuves.

Assembly

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

Virtual machine description

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

On initialization, the machine expects to receive :

initial values in its input registers, depending on the event.
a sequence of instructions which will be the code interpreted by the machine. This sequence is broken down into 16-bit words in an array, with the first word at index 0 of the array.

The machine behaves like a small processor, whose list of supported operations is given in the following summary table.

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.

To prevent infinite loops, the number of instructions that can be executed is limited (65536 by default).

If the machine encounters an error, it stops execution. An error can be a register overflow or one of the conditions listed in the summary table below.

Debugging

Locally, you can debug the virtual machine using the debugCode method. This method displays the state of the machine for each instruction. Users are free to redirect this display to a file, or to modify the function to step through program execution.

Instructions list

Overview table

Family	Operation	Assembler	Updates	Action	Error
Move	Move	`MOV Rj, op2`	-	`Rj = op2`
	Get RR from coprocessor	`MOVRR Rj`	-	`Rj = RR`	no prior FP
Load	Move from code (`1` word)	`MOVCW Rj`	-	`Rj = @Rj`	`Rj < 0` or `Rj>=l`
	Move from code (`Ri` words)	`MOVC Rj, Ri`	-	`Rj = @Rj`	`Rj < 0` or `Rj+Ri>=l` or `Ri<=0`
Logical	AND	`AND Ro, Rm, Rn`	-	`Ro = Rm & Rn`	`Rm < 0` or `Rn < 0`
	OR	`OR Ro, Rm, Rn`	-	`Ro = Rm \| Rn`	`Rm < 0` or `Rn < 0`
	XOR	`XOR Ro, Rm, Rn`	-	`Ro = Rm ^ Rn`	`Rm < 0` or `Rn < 0`
	Shift right	`SRL Ro, Rm, Rn`	-	`Ro = Rm >> Rn`	`Rn < 0`
	Shift left	`SLL Ro, Rm, Rn`	-	`Ro = Rm << Rn`	`Rn < 0`
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`
	Exact Division	`EDIV Ro, Rm, Rn`	-	`Ro = Rm // Rn`	`Rn<=0` or `Rm<0` or `Rm!=0[Rn]`
	GCD	`GCD Ro, Rm, Rn`	-	`Ro = gcd(Rm,Rn)`
	Primality Test	`MR Rj`	`Z`	`Z=True` if `Rj`is prime
Modular	Modular reduction	`MOD Rj, Ri`	-	`Rj = Ri mod RD`	`RD<=0`
	Modular exponentiation	`POW Rj, Ri`	-	`Rj = Ri**RC mod RD`	`RD<=0` or `RC < 0`
	Modular inversion	`INV Rj, Ri`	-	`Rj = Ri**(-1) mod RD`	`RD<=0`
	Coprocessor initialisation	`FP Rj, Ri`	-	`FPmodule: Rj` `size: Ri`	`Rj&1=0` or `Rj<=0` or `Ri=0`
	Coprocessor initialisation	`FPRR Ro, Rm, Rn`	-	`RR:Ro` `FPmodule: Rm` `size: Rn`	`Rm&1=0` or `Rm<=0` or `Rn=0`
	Montgomery Multiplication	`MM Ro, Rm, Rn`	-	`Ro = Rm*Rn/R mod FPmodule`	no prior FP or `Rm<0` or `Rn<0`
	Montgomery Multiplication	`MM1 Rj, Ri`	-	`Rj = Ri/R mod FPmodule`	no prior FP or `Rm<0` or `Rn<0`
	Montgomery Exponentiation	`MPOW Rj, Ri`	-	`Rj = (Ri/R)*RCR mod FPmodule`	no prior FP or `RC < 0`
Random	Random	`RND Rj`	-	`Rj = rand < 2**(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 = adest`	`PC>=l` or `PC < 0`
Call (Relative)	Call	`CR rdest`	-	`LR = PC, PC += rdest`	`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]+
dest = Ri, [a-zA-Z]+, #[0-9]+, #0x[0-9a-fA-F]+
0 <= adest < 65536
-128 <= rdest < 128, encoded on a signed byte
cst = [0-9]+, 0x[0-9a-fA-F]+

After a # the number must be able to be represented on up to 16 bits.

Special registers:

RC is used as the exponent
RD is used as the module
RE is used as the Link Register
RF is used as the Program Counter

Example code

abc:                        ;entry point, as first byte of generated bytecode
    MOV     R0, #0x00       ;assign constant value 0 to R0
    MOV     R1, #1          ;assign constant value 1 to R1
    MOV     R2, R1          ;assign R1 to r2
    MOV     R3, =constants  ;assign address of the tabular to R3
    MOVCW   R3              ;read first word from 'constants' tabular
    JR      startLoop       ;jump to relative address startLoop (offset from PC)
loop:
    ADD     R0, R1, R0      ;Add R1 to R0, result in R0. Not updating flags
startLoop:
    SUB     R2, R2, R1      ;subtract R1 (worth 1 here) from R2. Update flags
    JCR     loop            ;relative jump if carry, may be out range of relative offset if body of the loop is too huge
    STP                     ;end of programm

constants:                  ;some constants values
    .word 0x1234, 0x5678, =loop

Instruction details

MOV Rj, op2

Rj = op2

MOV Rj, =label

Rj = @label

AND Ro, Rm, Rn

Ro = Rm & Rn

See overview table for error conditions.

OR Ro, Rm, Rn

Ro = Rm | Rn

See overview table for error conditions.

XOR Ro, Rm, Rn

Ro = Rm ^ Rn

See overview table for error conditions.

SRL Ro, Rm, Rn

Ro = Rm >> Rn

See overview table for error conditions.

SLL Ro, Rm, Rn

Ro = Rm << Rn

See overview table for error conditions.

BTL Rj, Ri

Rj = bit_len(Ri)

ADD Ro, Rm, Rn

Ro = Rm + Rn

SUB Ro, Rm, Rn

Ro = Rm - Rn

Update 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

Update one boolean Z:

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

DIV Ro, Rm, Rn

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

See overview table for error conditions.

MOD Rj, Ri

Rj = Ri mod module

See overview table for error conditions.

POW Rj, Ri

Rj = Ri**exponent mod module

See overview table for error conditions.

GCD Ro, Rm, Rn

Ro = gcd(Rm,Rn)

INV Rj, Ri

Rj = Ri**(-1) mod module

See overview table for error conditions.

RND Rj

Rj = random de taille Rj bits (au plus 8192 bits)

See overview table for error conditions.

CMP Rj, Ri

Update two 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 significative byte of the value.

See overview table for error conditions.

MOVC Rj, Ri

Rj = @Rj

Ri indicates the number of words to be read from address Rj. The word at address Rj is the most significative byte of the value.

See overview table for error conditions.

JZA dest

PC = dest if Z = True

See overview table for error conditions.

JNZA dest

PC = dest if Z = False

See overview table for error conditions.

JZR dest

PC += dest if Z = True

See overview table for error conditions.

JNZR dest

PC += dest if Z = False

See overview table for error conditions.

JCA dest

PC = dest if C = True

See overview table for error conditions.

JNCA dest

PC = dest if C = False

See overview table for error conditions.

JCR dest

PC += dest if C = True

See overview table for error conditions.

JNCR dest

PC += op2 if C = False

See overview table for error conditions.

JA dest

PC = dest

See overview table for error conditions.

JR dest

PC += dest

See overview table for error conditions.

CA op2

LR = adresse de retour (PC)
PC = dest

See overview table for error conditions.

CR dest

LR = adresse de retour (PC)
PC += dest

See overview table for error conditions.

RET

PC = LR

See overview table for error conditions.

STP

Fin du programme

EDIV Ro, Rm, Rn

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

See overview table for error conditions.

MR Rj

Update boolean Z:

Z = True if Rj est un nombre probablement premier, else Z = False

FP Rj, Ri

Initializes a hardware coprocessor dedicated to Montogmery arithmetic calculations. The value of Rj is copied into an internal register designated by the name FPmodule. The value of Ri indicates the minimum working size, in bits. The working size is a multiple of 64 bits, and 3 bits of margin are taken from the minimum size passed as input. The actual working size is therefore: WorkingSize = 64*[(Ri+3)//64].

At initialization, two constants are calculated. An internal constant and the constant RR which is 4**WorkingSize mod FPmodule. RR is the square of the constant R.

See overview table for error conditions.

FPRR Ro, Rm, Rn

Similar to the FP function, but where the value RR is already known, passed as input and therefore does not need to be calculated. Ro contains the value RR, Rm contains the module and Rn the minimum working size.

See overview table for error conditions.

MOVRR Rj

Copies value RR to register Rj.

See overview table for error conditions.

MM Ro, Rm, Rn

Ro = Rm*Rn/R mod FPmodule

Calculate the Montogmery product of Rm and Rn.

See overview table for error conditions.

MM1 Rj, Ri

Rj = Ri/R mod FPmodule

Calculate the Montogmery product of Ri by 1.

See overview table for error conditions.

MPOW Rj, Ri

Rj = R*(Ri/R)**exposant mod FPmodule

Performs exponentiation with Montgomery products using the exponent stored in the RC register.

See overview table for error conditions.