Red Star OS is the Linux based OS created by the glorious Supreme Leader and his exquisite Information technology development team at the Korean Computer Center. Version 3.0 was released in the summer of 2012 and subsequently leaked internationally by Zammis Clark (also known as wack0).
A particularly interesting detail is the addition of kernel modules that are specifically designed to handle cryptographic operations. They allow the operating system to perform encryption, decryption, and other cryptographic functions “securely”.
By having these modules integrated into the kernel, the OS ensures that cryptographic operations are efficiently executed within the operating system itself, providing a higher level of security and performance. In this case, security refers to protection from user tampering, this is also thanks to the protection offered by SELinux.
Red Star OS includes cryptographic kernel modules: Jipsam1, Jipsam2 and Pilsung. These ciphers are all based on AES, but include some modifications.
The jipsam modules are present in Red Star OS 2.0, whereas Pilsung is present only in Red Star OS 3.0.
The most complex of these is Pilsung, which uses key-dependent S-Boxes and permutations. In particular, the ShiftRows operation of AES is replaced with a pseudo-random permutation, which is selected based on the round key.
In North Korean (and more broadly in Korean martial arts context), “pilsung” (필승) means “certain victory” or “sure victory”. It is often used as a motivational term to inspire confidence and determination, signifying an unwavering belief in achieving victory.
package pilsung
// Multiply by x modulo x^8 + x^4 + x^3 + x + 1
func xtime(b byte) byte {
if b&0x80 != 0 {
return (b << 1) ^ 0x1b
}
return b << 1
}
// GF(2^8) generic multiplication, double-and-add
func multiply(a byte, b byte) byte {
var c byte = 0x0
for i := 0; i < 8; i++ {
if ((b >> i) & 1) != 0 {
c ^= a
}
a = xtime(a)
}
return c
}
// Rotate Left
func rotateLeft(x byte, c int) byte {
return (x << c % 8) | (x >> (8 - c) % 8)
}
// Unmodified AES S-box
func subByte(x0 byte) byte {
x1 := multiply(x0, x0) // x^2
x2 := multiply(x1, x0) // x^3
x3 := multiply(x2, x2) // x^6
x4 := multiply(x3, x3) // x^12
x5 := multiply(x4, x2) // x^15
x6 := multiply(x5, x5) // x^30
x7 := multiply(x6, x6) // x^60
x8 := multiply(x7, x2) // x^63
x9 := multiply(x8, x8) // x^126
x10 := multiply(x9, x0) // x^127
x11 := multiply(x10, x10) // x^254 = x^-1
return x11 ^ rotateLeft(x11, 1) ^ rotateLeft(x11, 2) ^
rotateLeft(x11, 3) ^ rotateLeft(x11, 4) ^ 0x63
}
// Rotate the word
func rotWord(w [4]byte) [4]byte {
t := w[0]
w[0] = w[1]
w[1] = w[2]
w[2] = w[3]
w[3] = t
return w
}
// Subtract the word
func subWord(w [4]byte) [4]byte {
for i := 0; i < 4; i++ {
w[i] = subByte(w[i])
}
return w
}
// Sort array p of size n according to 0-1 array s
// Assumes s has n / 2 zeros and n / 2 ones
func getOne(s []byte, p []byte) []byte {
a := 0
b := 0
buf := p
for i := 0; i < len(p); i++ {
if s[i] != 0x00 {
buf[len(p)/2+a] = p[i]
a++
} else {
buf[b] = p[i]
b++
}
}
return p
}
type blockT [4][4]byte
// Mix block columns
func (block *blockT) mixColumns() {
for i := 0; i < 4; i++ {
c0 := block[i][0]
c1 := block[i][1]
c2 := block[i][2]
c3 := block[i][3]
block[i][0] = xtime(c0^c1) ^ c1 ^ c2 ^ c3
block[i][1] = c0 ^ xtime(c1^c2) ^ c2 ^ c3
block[i][2] = c0 ^ c1 ^ xtime(c2^c3) ^ c3
block[i][3] = xtime(c0^c3) ^ c0 ^ c1 ^ c2
}
}
// Add round key to block
func (block *blockT) addRoundKey(k [4][4]byte) {
for i := 0; i < 4; i++ {
for j := 0; j < 4; j++ {
block[i][j] ^= k[i][j]
}
}
}
// Sub bytes to block
func (block *blockT) subBytes(ctx *pilsungCtx, round int) {
for i := 0; i < 4; i++ {
for j := 0; j < 4; j++ {
block[i][j] = ctx.sboxes[round][i][j][block[i][j]]
}
}
}
// Shift block rows
func (block *blockT) shiftRows(ctx *pilsungCtx, round int) {
var copy [16]byte
for i := 0; i < 4; i++ {
for j := 0; j < 4; j++ {
copy[i*4+j] = block[i][j]
}
}
for i := 0; i < 4; i++ {
for j := 0; j < 4; j++ {
block[i][j] = copy[ctx.pboxes[round][i*4+j]]
}
}
}
package pilsung
// Pilsung Context
type pilsungCtx struct {
sboxXorConstant byte // 3
sboxes [30][4][4][256]byte // S-Boxes
pboxes [30][16]byte // P-Boxes
currentPermutation8 [8]byte // used for temporary storage
eKey [240]byte // AES scheduled key
}
// Permute the bits of inputMask according to the computed permutation
func (ctx *pilsungCtx) getPeSb(inputMask byte) byte {
var x byte = 0x0
for i := 0; i < 8; i++ {
if ((1 << i) & inputMask) != 0x0 {
x |= 1 << ctx.currentPermutation8[i]
}
}
return x ^ ctx.sboxXorConstant
}
// Generate a random permutation of [0:7] at ctx.currentPermutation8
func (ctx *pilsungCtx) getP8forSEnc(inputMask byte) {
var (
coinflips [24]byte
v0 byte = treeInteger8[inputMask%70]
v1 byte = (treeInteger4[(inputMask&0x0F)%6] << 0) | (treeInteger4[(inputMask>>4)%6] << 4)
)
for i := 0; i < 8; i++ {
coinflips[i] = (v0 >> (7 - i)) & 1
}
for i := 0; i < 8; i++ {
coinflips[i+8] = (v1 >> (7 - i)) & 1
}
for i := 0; i < 8; i += 2 {
if (inputMask & (3 << i)) != 0x0 {
coinflips[16+i+0] = 1
coinflips[16+i+1] = 0
} else {
coinflips[16+i+0] = 0
coinflips[16+i+1] = 1
}
}
// Initialize permutation with identity
for i := 0; i < 8; i++ {
ctx.currentPermutation8[i] = byte(i)
}
// Iterative version of the Rao-Sandelius shuffle
for i := 0; i < 3; i++ {
bins := 1 << i
size := 1 << (3 - i)
for j := 0; j < bins; j++ {
s := coinflips[i*8 : i*8+7]
p := ctx.currentPermutation8[j*size : j*size+size-1]
copy(ctx.currentPermutation8[:], getOne(s, p)[:])
}
}
}
// Generate a random permutation of [0:15] at output
func getP16Enc(input [16]byte) [16]byte {
var (
coinflips [64]byte
output [16]byte
)
// coin flips for first level
for i := 0; i < 4; i++ {
v0 := treeInteger4[(input[i]^input[i+4])%6]
for j := 0; j < 4; j++ {
coinflips[4*i+j] = (v0 >> (3 - j)) & 1
}
}
// coin flips for second level
for i := 0; i < 8; i++ {
if ((input[i] >> i) & 1) != 0 {
coinflips[16+2*i+0] = 1
coinflips[16+2*i+1] = 0
} else {
coinflips[16+2*i+0] = 0
coinflips[16+2*i+1] = 1
}
}
// coin flips for third level
for i := 0; i < 4; i++ {
v1 := treeInteger4[(input[i+8]^input[i+12])%6]
for j := 0; j < 4; j++ {
coinflips[32+4*i+j] = (v1 >> (3 - j)) & 1
}
}
// coin flips for fourth level
for i := 0; i < 8; i++ {
if ((input[8+i] >> i) & 1) != 0 {
coinflips[48+2*i+0] = 1
coinflips[48+2*i+1] = 0
} else {
coinflips[48+2*i+0] = 0
coinflips[48+2*i+1] = 1
}
}
// Initialize permutation with identity
for i := 0; i < 16; i++ {
output[i] = byte(i)
}
// Iterative version of the Rao-Sandelius shuffle
for i := 0; i < 4; i++ {
bins := 1 << i // number of subgroups
size := 1 << (4 - i) // size of each subgroup
for j := 0; j < bins; j++ {
s := coinflips[i*16 : i*16+15]
p := output[j*size : j*size+size-1]
copy(output[:], getOne(s, p)[:])
}
}
return output
}
// Generate all necessary S-boxes
func (ctx *pilsungCtx) getVSboxAll() {
for rounds := 1; rounds < gRoundCnt; rounds++ {
for i := 0; i < 4; i++ {
for j := 0; j < 4; j++ {
ctx.getP8forSEnc(ctx.eKey[j+4*i+16*rounds])
for k := 0; k < 256; k++ {
ctx.sboxes[rounds][i][j][k] = ctx.getPeSb(subByte(byte(k)))
}
}
}
}
}
// Generate all necessary P-boxes
func (ctx *pilsungCtx) getVPboxAll() {
for rounds := 1; rounds < gRoundCnt; rounds++ {
var roundScheduledKey [16]byte
copy(roundScheduledKey[:], ctx.eKey[16*rounds:16*rounds+15])
ctx.pboxes[rounds] = getP16Enc(roundScheduledKey)
}
}
// Initialize the xor constant
func (ctx *pilsungCtx) initVar() {
ctx.sboxXorConstant = xorConstant
}
// Generate the encryption permutations
func (ctx *pilsungCtx) genEncPerm() {
ctx.initVar()
ctx.getVSboxAll()
ctx.getVPboxAll()
}
package pilsung
import "crypto/sha1"
// Pilsung tweaked hashing function
func shaSign(in []byte) []byte {
var out = []byte{}
for i := 0; i < len(in); i += 16 {
// Pass 16 bytes through SHA-1
blocklen := 16
if i+blocklen > len(in) {
blocklen = len(in) - i
}
digest := sha1.Sum(in[i : i+blocklen])
// Pilsung's tweak to SHA-1
for i := 0; i < 20; i += 4 {
digest[i+3] ^= 0xFF
}
for i := 0; i < blocklen; i++ {
out = append(out, digest[i])
}
}
return out
}
// This is the KDF
func shaKey(in []byte, outlen int) []byte {
var out = []byte{}
if len(in) <= outlen {
return shaSign(in)
}
// Limit the dimension of the key
maxlength := 256
if len(in) < 256 {
maxlength = len(in)
}
// Pass the chunk though the custom hash function
for i := 0; i < maxlength; i += 32 {
chunklen := 32
if i+chunklen > maxlength {
chunklen = maxlength - i
}
buffer := shaSign(in[i : i+chunklen])
for j := 0; j < chunklen; j++ {
out[i+j] = in[i+j] ^ buffer[j]
}
}
return out
}
// This is the AES key schedule
func (ctx *pilsungCtx) expandRoundkey(k []byte, Nr int) {
var (
Nk int = Nr - 6 // 5
rcon byte = 1
)
for i := 0; i < Nk; i++ {
for j := 0; j < 4; j++ {
ctx.eKey[i*Nk+j] = k[4*i+j]
}
}
for i := Nk; i < 4*(Nr+1); i++ {
var temp [4]byte
for j := 0; j < 4; j++ {
temp[j] = ctx.eKey[(i-1)*Nk+j]
}
if i%Nk == 0 {
temp = rotWord(temp)
temp = subWord(temp)
temp[0] ^= rcon
rcon = xtime(rcon)
} else if Nk > 6 && i%Nk == 4 {
temp = subWord(temp)
}
for j := 0; j < 4; j++ {
ctx.eKey[i*Nk+j] = ctx.eKey[(i-Nk)*Nk+j] ^ temp[j]
}
}
}
// Key schedule wrapper
func (ctx *pilsungCtx) expandKey(k []byte) {
derived := shaKey(k, gCryptoKeyLen)
ctx.expandRoundkey(derived, gRoundCnt)
}
// Get the key for the current round in the right format
func (ctx *pilsungCtx) formatKey(round int) [4][4]byte {
var output [4][4]byte
for i := 0; i < 4; i++ {
for j := 0; j < 4; j++ {
output[i][j] = ctx.eKey[16*round+4*i+j]
}
}
return output
}
package pilsung
const (
gCryptoKeyLen = 32 // 256-bit key
gRoundCnt = 11 // 11 rounds
xorConstant = 3 // S-box Xor Constant
)
var (
// All combinations of 4 bits in 8-bit words
treeInteger8 = [70]byte{
0x0F, 0x87, 0x47, 0x27, 0x17, 0xC3, 0x63, 0x33, 0x1B, 0xA3,
0x53, 0x2B, 0x93, 0x4B, 0x8B, 0xE1, 0x71, 0x39, 0x1D, 0xB1,
0x59, 0x2D, 0x99, 0x4D, 0x8D, 0xD1, 0x69, 0x35, 0xA9, 0x55,
0x95, 0xC9, 0x65, 0xA5, 0xC5, 0xF0, 0x78, 0x3C, 0x1E, 0xB8,
0x5C, 0x2E, 0x9C, 0x4E, 0x8E, 0xD8, 0x6C, 0x36, 0xAC, 0x56,
0x96, 0xCC, 0x66, 0xA6, 0xC6, 0xE8, 0x74, 0x3A, 0xB4, 0x5A,
0x9A, 0xD4, 0x6A, 0xAA, 0xCA, 0xE4, 0x72, 0xB2, 0xD2, 0xE2,
}
// All combinations of 2 bits in 4-bit words
treeInteger4 = [6]byte{
0x03, 0x09, 0x05, 0x0C, 0x06, 0x0A,
}
)
// Export the Encryption function
func Encrypt(input [16]byte, key []byte) [16]byte {
var (
block blockT
ctx pilsungCtx
output [16]byte
)
// Set the key
ctx.expandKey(key)
ctx.genEncPerm()
// Array to matrix
for i := 0; i < 4; i++ {
for j := 0; j < 4; j++ {
block[i][j] = input[i*4+j]
}
}
// First round
block.addRoundKey(ctx.formatKey(0))
// Middle rounds
for round := 1; round < 10; round++ {
block.subBytes(&ctx, round)
block.shiftRows(&ctx, round)
block.mixColumns()
block.addRoundKey(ctx.formatKey(round))
}
// Last round
block.subBytes(&ctx, 10)
block.shiftRows(&ctx, 10)
// No mixColumns
block.addRoundKey(ctx.formatKey(10))
// Matrix to array
for i := 0; i < 4; i++ {
for j := 0; j < 4; j++ {
output[i+4+j] = block[i][j]
}
}
return output
}
Pilsung is coded around the assumption that AES with actual random S-boxes is provably secure against large classes of attacks, given enough rounds.
An S-box (Substitution box) is a fundamental component in symmetric key algorithms, particularly in block ciphers. It performs substitution, a form of non-linear transformation, which is crucial for introducing complexity and confusion into the encryption process.
S-boxes provide non-linear transformations which are essential for cryptographic strength. This non-linearity helps in thwarting linear cryptanalysis, a method used to break ciphers.
Introduced by Claude Shannon, confusion is a cryptographic principle aimed at obscuring the relationship between the plaintext, the ciphertext, and the key. S-boxes achieve this by substituting input bits with output bits in a non-linear manner.
While more directly associated with P-boxes (Permutation boxes), S-boxes also contribute indirectly to diffusion by ensuring that small changes in the input lead to significant changes in the output.
An S-box takes a fixed number of input bits and transforms them into a fixed number of output bits.
The transformations are typically defined in a lookup table format, where each possible input value maps to a specific output value.
S-boxes can be static (fixed) or dynamic. Static S-boxes are predefined and do not change, whereas dynamic S-boxes can be generated based on certain parameters, such as the key.
The AES S-box output is derived from the multiplicative inverse over a finite field combined with an affine transformation. This construction ensures strong resistance to both linear and differential cryptanalysis.
Designing secure S-boxes is a complex task, as poorly designed S-boxes can introduce vulnerabilities. A well-designed S-box should have high non-linearity to resist linear attacks, good avalanche effect (a small change in the input results in a significant change in the output) and resistance to known cryptographic attacks.
