(19) United States
`(12) Patent Application Publication (10) Pub. No.: US 2015/0372806 A1
`Carter et al.
`(43) Pub. Date:
`Dec. 24, 2015
`
`US 20150372806A1
`
`(54) ENCRYPTING OPERATING SYSTEM
`(71) Applicant: Exit-Cube (Hong-Kong) Limited,
`Central Hong Kong (HK)
`(72) Inventors: Ernst B. Carter, Fremont, CA (US);
`Vasily Zolotov, San Jose, CA (US)
`(21) Appl. No.: 14/751,304
`(22) Filed:
`Jun. 26, 2015
`O
`O
`Related U.S. Application Data
`(63) Continuation of application No. 13/776.266, filed on
`Feb. 25, 2013, now Pat. No. 9,098,712, which is a
`continuation of application No. 12/776,337, filed on
`May 7, 2010, now Pat. No. 8,407,761, which is a
`continuation of application No. 10/648,630, filed on
`Aug. 25, 2003, now Pat. No. 7,810,133.
`(60) Provisional application No. 60/405,459, filed on Aug.
`23, 2002.
`s
`
`Publication Classification
`
`(51) Int. Cl.
`H04L 9/06
`G06F2L/60
`
`(2006.01)
`(2006.01)
`
`(52) U.S. Cl.
`CPC ............ H04L 9/0618 (2013.01); G06F 21/602
`(2013.01); H04L 9/0681 (2013.01); H04L
`9/0625 (2013.01)
`
`ABSTRACT
`(57)
`A method of and system for encrypting and decrypting data
`on a computer system is disclosed. In one embodiment, the
`system comprises an encrypting operating system (EOS),
`which is a modified UNIX operating system. The EOS is
`configured to use a symmetric encryption algorithm and an
`encryption key to encrypt data transferred from physical
`memory to secondary devices, such as disks, Swap devices,
`network file systems, network buffers, pseudo file systems, or
`any other structures external to the physical memory and on
`which can data can be stored. The EOS further uses the
`symmetric encryption algorithm and the encryption key to
`decrypt data transferred from the secondary devices back to
`physical memory. In other embodiments, the EOS adds an
`extra layer of security by also encrypting the directory struc
`ture used to locate the encrypted data. In a further embodi
`ment a user or process is authenticated and its credentials
`checked before a file can be accessed, using a key manage
`ment facility that controls access to one or more keys for
`encrypting and decrypting data.
`
`12 Ns- sfin
`
`-----------r 16
`
`10
`
`114
`
`1F.
`1.
`
`is
`
`a des
`
`a
`
`1.
`
`1.
`System 1118
`1.
`Memory 1
`1.
`14---------TE-
`
`134
`
`126
`140
`------T-1 ge
`Protective Storage
`136
`
`- - - - - - -
`
`- - - - - - - 2
`
`- 1.
`
`P
`
`as
`t
`re
`
`122
`124
`
`efn
`
`128
`
`
`
`
`
`
`
`
`
`-
`1.
`
`|
`
`P
`
`|-
`
`efe k
`
`4-2
`138
`1.
`1
`1.
`Data Vault 1
`P - - - - - - - -
`/
`1.
`Key Vault 1
`
`efn
`
`efn k
`
`
`
`
`
`APPLE 1023
`
`1
`
`

`

`Patent Application Publication
`
`Dec. 24, 2015 Sheet 1 of 28
`
`US 2015/037280.6 A1
`
`1.
`
`/
`4-1 18
`System
`1.
`1.
`Memory1
`4- - - - - - - - - - - - - - -
`
`Sas
`
`122
`124
`
`134
`126
`2-----------, i.
`Protective Storage
`136 ------ 128
`1.
`-1
`4- or - og
`4. "Data vault.--
`efc
`efn
`2
`2.1. if key vault-
`|
`Fig. 1
`
`efe
`
`efn
`
`
`
`138
`
`1.
`
`1.
`
`efin
`
`
`
`
`
`
`
`----
`-1
`
`224
`
`14
`
`222
`
`Z
`
`21 O
`^
`
`1.
`P
`1.
`
`1.
`
`System
`Memory, 1
`
`1.
`(, 18
`
`140
`tri-------------m Lee
`: Protective Storagc
`216
`|
`1.
`
`as a
`
`4x
`
`a
`
`-
`
`-- - - -t.
`
`Ap
`
`P
`
`4. etc.
`
`2. Data Vault 1
`
`
`
`4.--
`1 :
`
`SE-122
`220
`
`
`
`2
`
`

`

`Patent Application Publication
`
`Dec. 24, 2015 Sheet 2 of 28
`
`US 2015/037280.6 A1
`
`File System
`
`Virtual
`
`3.18
`
`330
`
`Log Streams Device Driver
`
`Character Driver Switch
`
`320
`
`322
`
`324
`
`326
`
`Log Streams
`Device Driver
`
`Log Streams
`Device Driver
`
`Printer Device Network Device
`Driver
`
`Teletype
`Device
`
`410
`
`412
`
`
`
`44
`
`416
`
`418
`
`Directory Vault
`Management
`Sub-System
`
`Expert System for
`Data Control & Tracking
`Sub-System
`
`Traditional UNIX
`Kernel Services
`
`Virtual
`Memory
`Management
`
`
`
`File System
`S5 FS
`
`Log Streams
`Device Driver
`
`Encryption Key
`Management
`Sub-System
`
`FileName
`Management
`Sub-System
`
`Intelligent File
`Control
`Sub-System
`
`Directory Name
`Management
`Sub-System
`
`Administration
`Access Control
`Sub-System
`
`430
`
`Block Device Driver Switch
`
`Character Driver Switch
`
`432
`
`434
`
`Disk Storage
`Device Driver
`
`Tape System
`Device Driver
`
`Printet Drive
`Driver
`
`Network
`Device Driver
`
`Teletype
`Device Driver
`
`3
`
`

`

`Patent Application Publication
`
`Dec. 24, 2015 Sheet 3 of 28
`
`US 2015/037280.6 A1
`
`510
`k
`
`
`
`512
`
`Reasoning Engine
`
`Operating System Environment
`
`Computations:
`Security Concepts
`Heuristics
`Reasonable System Behaviors
`Inputs:
`Assertions (Asserted Behavior Patterns Observed)
`Outputs:
`Knowledge Asserted from Reasoning in the Form of Assertions
`
`
`
`
`
`
`
`
`
`Observer
`Observes patterns of
`Systern Commands
`Inputs:
`User Commands
`Outputs
`Pattern Matching
`
`
`
`
`
`
`
`
`
`520
`
`518
`
`Operating System Environment
`
`514
`
`
`
`
`
`
`
`
`
`
`
`Inference Engine
`
`Analytical Assertion from
`Reasoning System
`
`528
`
`534
`r
`Assertions
`
`User Commands & System Behavior
`Monitor
`
`Observations
`
`530
`
`Pattern Matching
`
`522
`t
`Inference
`
`
`
`524
`
`Assertions
`
`Feedback Loop
`
`Assertion Engine
`
`Inferences
`522
`
`2
`g
`:
`3 D
`C
`
`|
`
`; :
`23
`5 2
`32
`s
`5 5 2
`
`516
`
`Learning Engine
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Operating System Environment
`
`Future
`Behavior
`Predictions
`
`Past
`Apriori
`Behaviors
`
`Truth
`System
`yS
`
`Apriori
`Behaviors
`
`4
`
`

`

`Patent Application Publication
`
`Dec. 24, 2015 Sheet 4 of 28
`
`US 2015/037280.6 A1
`
`610
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`The Truth
`Based on
`Time T-1
`
`
`
`
`
`
`
`
`
`
`
`Gains
`Due to
`Corrections at
`Time T-1
`
`616
`
`648
`
`Gains
`and
`Adjustments
`
`The Truth
`Based on
`Time T-I-1
`
`Predictions
`about the
`Future
`
`614
`
`Fig. 6
`
`5
`
`

`

`Patent Application Publication
`
`Dec. 24, 2015 Sheet 5 of 28
`
`US 2015/037280.6 A1
`
`C)(E)(E)(2)
`
`0 I L
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Uuº]SKS ?IJA
`
`CHOET
`
`ZZ/
`
`6
`
`

`

`Patent Application Publication
`
`Dec. 24, 2015 Sheet 6 of 28
`
`US 2015/037280.6 A1
`
`
`
`19S KOSI
`
`
`
`I Kø>| pageIQU39
`
`
`
`
`
`
`
`
`
`7
`
`

`

`Patent Application Publication
`
`Dec. 24, 2015 Sheet 7 of 28
`
`US 2015/037280.6 A1
`
`910
`
`//
`
`
`
`
`
`932
`
`/
`
`To The Internet and
`Clearing House
`
`le Kbal)
`
`Encrypted Data) occo
`
`Data Not Encrypted
`
`o
`Transaction Broker
`
`Modem
`
`G)
`
`928
`E.Merchant
`
`Fig. 9
`
`8
`
`

`

`Patent Application Publication
`
`Dec. 24, 2015 Sheet 8 of 28
`
`US 2015/0372806 A1
`
`
`
`G)
`
`%
`
`0 I $1){
`
`9
`
`

`

`Patent Application Publication
`
`Dec. 24, 2015 Sheet 9 of 28
`
`US 2015/0372806 A1
`
`
`
`10
`
`

`

`Patent Application Publication
`
`Dec. 24, 2015 Sheet 10 of 28
`
`US 2015/037280.6 A1
`
`1210
`
`Key Entry
`me Entry Y. . -a - 1216
`Name Entry
`
`
`
`A.
`
`e
`
`Encryption 132 -1
`System
`1
`
`1218
`
`1226
`1.
`
`r-1224
`Key Entry
`Count
`T2 - 1220
`OLLC
`1.
`Entry go-1d.
`Encrytion
`1.
`Svst
`1.
`1.
`14----------1 1228
`
`1222
`
`efn
`
`
`
`
`
`
`
`--------- Le?e
`Protective Storage
`i
`-assessitz
`4.--
`A
`efn
`1.
`1
`efc
`Data vault -
`1 :
`- 2C
`1
`----------
`!- efc k
`efin k Key Vault 1
`--------------
`
`
`
`11
`
`

`

`Patent Application Publication
`
`Dec. 24, 2015 Sheet 11 of 28
`
`US 2015/037280.6 A1
`
`
`
`12
`
`

`

`Patent Application Publication
`
`Dec. 24, 2015 Sheet 12 of 28
`
`US 2015/037280.6 A1
`
`1310
`
`Page-Level
`Allocator
`
`1301
`
`1350
`
`
`
`Kernel Memory
`Allocator
`
`
`
`Networks
`Buffers
`
`Process
`Structures
`
`i-nodes, File
`Descriptors
`
`User Processes
`
`Block Buffer
`Cache
`
`1340
`
`1335
`
`1336
`
`1325
`
`1326
`
`Fig. 14
`
`13
`
`

`

`Patent Application Publication
`
`Dec. 24, 2015 Sheet 13 of 28
`
`US 2015/037280.6 A1
`
`1400
`
`Page 1
`
`Page 2
`
`Page 3
`
`Page 4
`
`Page 5
`
`Size x
`
`Size x
`
`Size X
`
`Size x
`
`140
`
`From Main Memory
`
`
`
`File Frags
`
`up a
`
`as H -
`
`Swap Storage
`
`C
`S. 1430
`
`1------- -
`
`Permanent
`Storage
`
`
`
`
`
`
`
`14
`
`

`

`Patent Application Publication
`
`Dec. 24, 2015 Sheet 14 of 28
`
`US 2015/037280.6 A1
`
`
`
`15
`
`

`

`Patent Application Publication
`
`Dec. 24, 2015 Sheet 15 of 28
`
`US 2015/037280.6 A1
`
`009 I
`
`
`
`
`
`809 I
`
`609 I
`
`16
`
`

`

`Patent Application Publication
`
`Dec. 24, 2015 Sheet 16 of 28
`
`US 2015/037280.6 A1
`
`
`
`
`
`17
`
`

`

`Patent Application Publication
`
`Dec. 24, 2015 Sheet 17 of 28
`
`US 2015/0372806 A1
`
`1800
`
`//
`
`
`
`1820
`1810
`
`1840
`
`1850
`
`1860
`
`1870
`
`Fig. 19
`
`18
`
`

`

`Patent Application Publication
`
`Dec. 24, 2015 Sheet 18 of 28
`
`US 2015/037280.6 A1
`
`3600
`
`-1
`
`i. 360
`
`3615
`
`
`
`19
`
`

`

`Patent Application Publication
`
`Dec. 24, 2015 Sheet 19 of 28
`
`US 2015/037280.6 A1
`
`SOGH
`
`
`
`
`
`
`
`
`
`20
`
`

`

`Patent Application Publication
`
`Dec. 24, 2015 Sheet 20 of 28
`
`US 2015/037280.6 A1
`
`Traverse Encrypted File
`Name Directory Unencrypting
`FileNames with First Key, Until
`Find Match
`
`1915
`
`
`
`
`
`
`
`
`
`
`
`
`
`Does User
`or Process have
`Permission?
`
`
`
`Log Improper
`Request
`
`1925
`
`
`
`
`
`
`
`Retrieve First I-node
`Number (Can be in List of Free
`Inodes if new File)
`
`1935
`
`1930
`
`Encrypt Data
`Using Second Key and Store Data
`
`1940
`
`1950
`
`21
`
`

`

`Patent Application Publication
`
`Dec. 24, 2015 Sheet 21 of 28
`
`US 2015/037280.6 A1
`
`2000
`
`Traverse Encrypted File
`Name Directory, Unencrypting
`FileNames with First key, Until
`Find a Match
`
`2005
`
`2010
`
`
`
`
`
`Does User
`or Process have
`ermission?
`
`No
`
`Log Improper
`Request
`
`2015
`
`
`
`Retrieve First I-node Number
`and Retrieve Data Using Direct, Single
`Double- and Triple-Indirect Pointers
`
`Greturn) 2020
`
`2025
`
`Decrypt Data Using Second Key
`
`2030
`
`Store in Read Buffer
`
`2035
`
`CReturn) 2040
`Fig. 23
`
`22
`
`

`

`Patent Application Publication
`
`Dec. 24, 2015 Sheet 22 of 28
`
`US 2015/037280.6 A1
`
`2110
`
`21 11
`
`21 12
`
`2113
`
`2100
`//
`
`2101
`
`
`
`2240
`
`Kernel Space
`
`2220
`
`2225
`2230 ----Hardware Interface
`
`Fig. 25
`
`23
`
`

`

`Patent Application Publication
`
`Dec. 24, 2015 Sheet 23 of 28
`
`US 2015/037280.6 A1
`
`2300
`
`-1
`
`2305
`
`2310
`
`2340
`
`2350
`
`(
`
`File System
`
`)."
`
`Layer
`
`SEC)
`
`Layer
`
`Swap Device
`
`la
`
`2315
`
`
`
`Physical
`Memory
`
`2320
`
`Layer
`
`2330
`
`Struct
`proc
`
`Address Dy
`Layer
`
`2355
`
`2335
`
`Hat
`Layer
`
`2325
`
`Fig. 26
`
`24
`
`

`

`Patent Application Publication
`
`Dec. 24, 2015 Sheet 24 of 28
`
`US 2015/0372806 A1
`
`2400
`
`
`
`
`
`
`
`
`
`
`
`Offset in the Vinode
`
`Hash Chain Pointer
`
`Pointers for Vinode page List
`
`Pointers for Free List or I/O List
`
`Hat-Related Information
`
`
`
`
`
`Fig. 27
`
`25
`
`

`

`Patent Application Publication
`
`Dec. 24, 2015 Sheet 25 of 28
`
`US 2015/0372806 A1
`
`2510
`
`2500
`
`//
`
`250 N- User Process
`
`2503
`
`Data Access
`(page fault)^2502
`
`File Access
`(page fault)
`
`
`
`vop read
`VOO Write
`p
`
`Address Space Layer
`
`
`
`
`
`as fault
`
`File Subsystem
`
`Segmap fault
`
`
`
`
`
`Vop getpage
`
`
`
`
`
`
`
`Vop putpage
`
`High-Level
`Vinode-ops
`
`Low-Level
`Vinode-ops
`
`VM Subsystem
`
`
`
`2520
`
`2530
`
`Fig. 28
`
`2540
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`26
`
`

`

`Patent Application Publication
`
`Dec. 24, 2015 Sheet 26 of 28
`
`US 2015/037280.6 A1
`
`08990Z99)
`
`Vo
`er
`er
`
`co
`
`Nd
`S.
`
`er
`
`0099
`
`1099
`
`| JºJJIl{{ | |-——————|
`
`
`
`
`
`
`
`27
`
`

`

`Patent Application Publication
`
`Dec. 24, 2015 Sheet 27 of 28
`
`US 2015/037280.6 A1
`
`S 169
`
`0069
`
`
`
`
`
`
`
`
`
`
`
`
`
`(ºpoo osueo!!) CII anb?un uønsÁS SO?I - CITSOGI
`
`
`
`
`
`
`
`[06%
`
`Z06%
`
`8.06%
`
`0.16%
`
`0.96%
`
`28
`
`

`

`Patent Application Publication
`
`Dec. 24, 2015 Sheet 28 of 28
`
`US 2015/037280.6 A1
`
`3200
`A-1
`3217
`ko's Kiss) (Kaisaka ia (ka'is) (k'is) Ko?sa (ki'sa-3.0
`
`3212
`
`3213
`
`3214
`
`3215
`
`3216
`
`3210
`
`3211
`
`3218
`
`BN - Number of
`1024-bit block of file
`
`Permutation
`Function
`pf) (BN) D7
`
`3219
`
`3221
`
`3222
`
`3223
`
`3224
`
`3225 3226 3227
`
`3228
`
`Koo Kolka Koikeit) kits. Koils) kero?)-320
`Dope (Dis) (D22s) (Dis)|D: ) (D32) Dors) (D72)-32so
`
`3231
`
`3232
`
`3233
`
`3234
`
`3235 3236
`
`3237
`
`3238
`
`AES
`Standard
`
`3240
`
`3242
`
`3243
`
`3244
`
`3245
`
`3246
`
`3247
`
`3248
`
`3249
`
`U0. 64|U1. Glu2.64U3. Galus. 64Us clug. 64|Unca
`325
`3252 3253 As A K 32.58
`
`“...
`
`.
`
`... 3250
`
`32.59 3260
`
`3261 3262
`
`
`
`BN -- Number of
`1024-bit block offil
`024-bit block of file
`
`A
`
`Permutation
`Function
`C1
`pfo (BN)
`
`
`
`
`
`3271 3272 3273 3274 3275 3276 3277 3278 3279 3280
`Fig. 31
`
`328 3282
`3290
`
`
`
`
`
`29
`
`

`

`US 2015/037280.6 A1
`
`Dec. 24, 2015
`
`ENCRYPTING OPERATING SYSTEM
`
`RELATED APPLICATIONS
`0001. This application is a continuation of the co-pending
`U.S. patent application Ser. No. 13/776.266, filed Feb. 25,
`2013, and titled “ENCRYPTING OPERATING SYSTEM
`which is a continuation of the U.S. patent application Ser. No.
`12/776,337, filed May 7, 2010, and titled “ENCRYPTING
`OPERATING SYSTEM, which is a continuation of U.S.
`patent application Ser. No. 10/648,630, filed Aug. 25, 2003,
`and titled “ENCRYPTING OPERATING SYSTEM, which
`claims priority from U.S. provisional patent application Ser.
`No. 60/405,459, filed Aug. 23, 2002, and titled “ENCRYPT
`ING OPERATING SYSTEM, all of which are hereby incor
`porated by reference.
`
`FIELD OF THE INVENTION
`0002 This invention relates to the field of computer oper
`ating systems. More specifically, this invention relates to
`operating systems used to automatically encrypt and decrypt
`data transferred between computer memory and secondary
`devices.
`
`BACKGROUND OF THE INVENTION
`0003 Information technology, in the form of computer
`systems, is a pervasive and critically important aspect of
`modern Society. The appropriate and correct operations of
`these systems is just as essential for the Smallest of individual
`efforts as it is for the greatest enterprises and governments.
`Data security is one of the paramount issues that impacts the
`acceptability of a computer system's operations. Keeping
`data secure includes both being able to selectively restrict
`access to and the use of data, as well as maintain and protect
`data from unauthorized modification or destruction. Beyond
`solely safeguarding the use and integrity of the data stored,
`data security also affects the overall security of the computer
`system as a whole. For example, compromised permissions
`data can facilitate unauthorized use of computer system
`resources, and even malicious damage to its operations. Addi
`tionally, virtually all large scale endeavors are implemented
`in concert with computer systems, and the endeavors them
`selves can be hampered or worse by degraded data security.
`The ascendance to prominence of the Internet, and other
`large-scale computer networks, has further magnified the
`consequences of data security flaws.
`0004. Approaches to the security of computer data have
`generally taken two paths, controlling the access to data and
`encrypting the data to prevent its reading by an unauthorized
`entity. Among the tactics for controlling access are passwords
`or other information based restrictions, and firewalls or other
`hardware based portal restrictions. Encryption based security
`methods endeavor to prohibit data from being comprehended
`if accessed without proper authorization. For the ever-in
`creasing benefits of large Scale public and private networks to
`be realized, substantial Volumes of communication both
`within and between these networks is vital. The speed and
`ease of these communications directly correlates with the
`benefits garnered from them, and is inversely related to the
`security of the communicating systems’ data. The value being
`realized from communications between computer systems is
`too great for the institution of substantial hardware-based
`restrictions to become a viable alternative for protecting data.
`A popular alternative is information-based access controls,
`
`such as passwords. The Vulnerabilities of information-based
`access controls to security lapses are evident from the billions
`of dollars in damages caused by computer viruses that are
`spread over the Internet and malicious attacks on Web sites.
`0005. The first step towards more substantially protecting
`a computer system requires ensuring the security of the sys
`tems data. The ability to comprehend the data can be selec
`tively controlled with encryption. Encryption methods gen
`erally utilize a mathematical algorithm to transform the
`legible data (plaintext) into an encrypted form (ciphertext),
`that can not be comprehended without the knowledge and use
`of a key to decrypt the encrypted form. The quality of the data
`protection relies on the complexity of the algorithm, plus the
`size and the safekeeping of the key. In 1972 the National
`Bureau of Standards, now the National Institute of Standards
`and Technology (NIST), issued the first public request for an
`encryption standard. The result was the Data Encryption
`Standard (DES). This 30-year old symmetric algorithm stan
`dard uses a 64-bit block cipher to encrypt data with a 56-bit
`private key. Recent advances in distributed key search tech
`niques have demonstrated that the DES 56-bit key, which is
`the source of security when using the DES, is too short for
`today's security applications.
`0006 An improvement on DES was accomplished with
`the use of Triple-DES. Triple-DES uses a 168-bit key which
`is broken into three different 56-bit keys that are used to
`Successively encrypt, then decrypt, and finally re-encrypt
`64-bit blocks with the DES algorithm. While an improvement
`on DES, Triple-DES shares the characteristic limitation of
`DES 64-bit block length, which is exposed to attacks when
`large amounts of data are encrypted under the same key. Due
`to the shortness of the 56-bit key, and the significant number
`of repeated encryptions necessary to handle large amounts of
`data with relatively small 64-bit blocks, patterns of encryp
`tion can repeat themselves, can become apparent and thus
`enable the key to be solved and the data compromised.
`0007. In response to the need for an improvement on DES,
`NIST announced the Advance Encryption Standard (AES)
`program in 1997. The AES program requested a larger block
`cipher. Block ciphers can be used to design stream ciphers
`with a variety of synchronization and error extension proper
`ties, one-way hash functions, message authentication codes,
`and pseudo-random number generators. Because of this flex
`ibility, block ciphers have become the workhorses of modern
`cryptography. Other design criteria specified by the NIST
`included a larger key length, a larger block size, faster execu
`tion speed, and greater flexibility. The NIST's intent was for
`the AES to become the standard symmetric block cipher
`algorithm of the next decade. In October, 2001, the NIST
`announced the approval of the Rijndael cipher, designed by
`Vincent Rijmen and Joan Daemen, as the Federal Information
`Processing Standard (PIPS) for the Advanced Encryption
`Standard, FIPS-197. Rijndael was chosen based primarily on
`its efficiency and low memory requirements.
`0008 Rijndael is a 128-bit symmetric block cipher that
`accepts a variable-length key of 128-, 192-, or 256-bits. The
`cipher is a 16-round Feistel network with a bijective F func
`tion made up of four key-dependent 8-by-8-bit S-boxes, a
`fixed 4 by 4 maximum distance separable matrix over GE, a
`pseudo-Hadamard transform, bitwise rotations, and a care
`fully designed key schedule. The design of both the round
`function and the key schedule permits a wide variety of
`tradeoffs between speed, data size, key setup time, and
`memory. Rijndael is a cryptoanalyzed algorithm which is
`
`30
`
`

`

`US 2015/037280.6 A1
`
`Dec. 24, 2015
`
`intended to be difficult to either reverse the engineering pro
`cess to find the keys or guess the code to break the system
`from the limited amounts of data available. The Rijndael
`algorithm is a now a well-known technology in the field of
`encryption, and is explicated in depth at the publicly acces
`sible NIST website “AES home page” at the worldwide web
`URL http://csrc.nist.gov/encryption/aes/.
`0009 Today’s computers can store and process data at
`ever increasing rates. This processing power makes them
`attractive to individuals and businesses, which use them to
`store and process personal data, hospital records such as
`patient histories, confidential business data, and other vital
`information. To ensure that the data is accessed by only autho
`rized users, the data can be protected in a variety of ways. For
`example, most computer systems require that a user enter a
`password or pass phrase before she can access the data. Addi
`tionally, the computer system can require that the user belong
`to a specific group that has been granted permission to access
`the data.
`0010. These systems have several drawbacks. First, if the
`storage device is removed from the computer system, an
`unauthorized user can access the data on secondary computer
`storage (e.g., a hard disk), bypassing the Security mechanism
`that relies on a password or pass phrase. Second, because
`passwords and pass phrases are often limited in length, com
`puter programs can be used to quickly try combinations of
`symbols to guess user-generated passwords and pass phrases
`to gain access to the storage device and thus the confidential
`data.
`0011. Several computer systems have offered various
`solutions. Some versions of the UNIX operating system, for
`example, Support the “crypt’ program, an application pro
`gram that requires the user to enter a password each time she
`wishes to store data on or retrieve data from a storage device.
`Other computer systems provide application programs that
`allow a user to enter a password each time she wishes to store
`or retrieve data. Still other application-based encryption sys
`tems encrypt whole file partitions and do allow encryption of
`individual files.
`0012. These application programs are inefficient for sev
`eral reasons. First, the application programs require the user
`to execute it when transferring data between computer
`memory and secondary memory, a time-consuming process.
`Second, the application program is inefficient, requiring a
`context Switch each time it traps to the kernel, which contains
`lower-level, hardware specific code for storing and retrieving
`data. The extra overhead of a context switch can slow the
`execution of the program that calls the encryption application
`program. Furthermore, these application programs can be
`pre-empted by kernel routines or by other applications having
`a higher priority. Third, these application programs are not
`always portable. They may not execute properly on platforms
`that do not support the application program.
`0013 What is needed is a method of and a system for
`encryption that is fast, seamless to the user, portable, and
`efficient.
`
`SUMMARY OF THE INVENTION
`0014. The present invention is directed to a system for and
`method of encrypting and decrypting data transferred
`between a computer's physical memory and a secondary
`device. Such as secondary storage. The system comprises an
`operating system having a kernel configured to encrypt and
`decrypt the data. Performing the encrypting and decrypting
`
`steps in a kernel provides a more efficient means of encrypt
`ing and decrypting data in a protected mode. The kernel is
`further configured to encrypt path names to the data, thus
`providing an additional level of security.
`0015. In a first aspect of the present invention, a computer
`operating system comprises a kernel that is configured to
`encrypt and decrypt data transferred between a computer
`memory and a secondary device. Preferably, the computer
`operating system is based on the UNIX operating system. In
`one embodiment, the kernel comprises an encryption engine.
`The encryption engine is configured to encrypt clear data to
`generate cipher data, and to decrypt the cipher data to gener
`ate the clear data. In another embodiment, the computer oper
`ating system further comprises a memory portion coupled to
`the encryption engine and configured to store the cipher data.
`In another embodiment, the encryption engine is configured
`to encrypt clear data and decrypt cipher data according to a
`symmetric encryption algorithm, such as the Rijndael algo
`rithm.
`0016. In a second aspect of the present invention, a com
`puter system comprises a first device and a second device.
`The first device has an operating system kernel configured to
`encrypt clear data using an encryption key to generate cipher
`data. The second device is coupled to the first device and
`configured to receive the cipher data from the first device and
`decrypt the cipher data to generate the clear data. Preferably,
`the operating system kernel is based on the UNIX operating
`system. In one embodiment, the operating system kernel is
`configured to encrypt the clear data using a symmetric algo
`rithm. Preferably, the symmetric algorithm comprises a block
`cipher, Such as a Rijndael algorithm. In another embodiment,
`the encryption key comprises at least 2048 bits. In another
`embodiment, the computer system further comprises a com
`munications channel coupling the first device to the second
`device. The communications channel can comprise a net
`work, such as a local area network (LAN) or the Internet.
`0017. In a third aspect of the present invention, a method
`of encrypting data comprises receiving clear data and execut
`ing kernel code in an operating system using a symmetrickey
`to encrypt the clear data to generate cipher data. In one
`embodiment, the symmetric key encrypts the clear data to
`generate cipher data according to a block cipher. Preferably,
`the block cipher comprises a Rijndael algorithm.
`0018. In a fourth aspect of the present invention, a com
`puter system comprises a processor, a memory device for
`storing data, and an operating system comprising a kernel.
`The kernel is configured to encrypt and decrypt data trans
`ferred between a physical memory and the memory device. In
`one embodiment, the kernel is configured to encrypt and
`decrypt data using an key management system that uses an
`encrypting algorithm such as the Rijndael algorithm.
`0019. In a fifth aspect of the present invention, a method of
`accessing a file comprises authenticating a user, checking the
`user's permission to access the file, and encrypting the file
`using an encryption key. In one embodiment, encrypting the
`file comprises dividing the file into a plurality of file seg
`ments, each file segment having an associated file segment
`number, dividing each file segment into a plurality of corre
`sponding file blocks, dividing the encryption key into a plu
`rality of corresponding encryption key segments, permutat
`ing the corresponding encryption key segments using the
`associated file segment number and a first permutation func
`tion to produce a corresponding intermediate key, encrypting
`the corresponding file blocks using an encryption algorithm
`
`31
`
`

`

`US 2015/037280.6 A1
`
`Dec. 24, 2015
`
`and the corresponding intermediate key to generate a corre
`sponding first encrypted data, and permutating the corre
`sponding first encrypted data using a second permutation
`function and the associated file number to generate corre
`sponding final encrypted data. Reversing the steps can be
`used to decrypt data. In one embodiment, the encryption
`algorithm comprises the Rijndael algorithm. In another
`embodiment, the first permutation function differs from the
`second permutation function. Preferably, each file segment is
`at least 1024-bits long and the encryption key is at least
`2048-bits long.
`
`BRIEF DESCRIPTION OF THE SEVERAL
`VIEWS OF THE DRAWINGS
`0020 FIG. 1 shows an encrypting operating system and
`computer memory, in accordance with the present invention.
`0021
`FIG. 2 shows an encrypting operating system and
`computer memory, in accordance with the present invention.
`0022 FIG. 3 shows the software components that form a
`traditional UNIX kernel.
`0023 FIG. 4 shows the software components that forman
`encrypting operating system in accordance with the present
`invention.
`0024 FIG. 5 is a block diagram showing the functions
`performed by an Expert Data Control System, in accordance
`with the present invention.
`0025 FIG. 6 is a block diagram showing the steps of a
`gains algorithm, in accordance with the present invention.
`0026 FIG. 7 is a block diagram showing the steps per
`formed by a Key Management System, inaccordance with the
`present invention.
`0027 FIG. 8 is a block diagram showing the steps per
`formed by a Key Management System, additionally showing
`an i-node table, in accordance with the present invention.
`0028 FIG. 9 is a schematic diagram showing a banking
`site and a merchant site configured to exchange encrypted
`data in accordance with the present invention.
`0029 FIG. 10 is a more detailed schematic diagram of the
`merchant site shown in FIG. 9.
`0030 FIG. 11 is a schematic diagram showing how a
`clearing house communicates with two banks and their cor
`responding merchants, in accordance with the present inven
`tion.
`FIG. 12 is a more detailed schematic of the steps
`0031
`shown in FIG. 1.
`0032 FIG. 13 is a high-level schematic diagram of a pro
`cess and a virtual memory system.
`0033 FIG. 14 is a block diagram of a memory allocation
`system.
`0034 FIG. 15 is a schematic diagram showing the rela
`tionship between a memory pool, virtual storage, and perma
`nent Storage.
`0035 FIG. 16 is a high-level diagram showing encryption
`and decryption across a network using NFS, in accordance
`with the present invention.
`0036 FIG. 17 shows a file system, including an i-node list
`and the related data blocks.
`0037 FIG. 18 is a high-level diagram showing virtual
`memory, on-disk i-nodes, and encrypted data on a disk, in
`accordance with embodiments of the present invention.
`0038 FIG. 19 shows a data structure containing access
`permissions, in accordance with embodiments of the present
`invention.
`
`0039 FIG. 20 is a high-level diagram of components of an
`EOS in accordance with the present invention.
`0040 FIG. 21 is a diagram showing the use of credentials
`and permissions in accordance with the present invention.
`0041
`FIG. 22 is a flow chart, showing the steps used to
`store encrypted data to disk, inaccordance with embodiments
`of the present invention.
`0042 FIG. 23 is a flow chart, showing the steps used to
`retrieve encrypted data from disk, in accordance with
`embodiments of the present invention.
`0043 FIG. 24 is a schematic diagram showing the rela
`tionship between user processes and device drivers, in accor
`dance with embodiments of the present invention.
`0044 FIG. 25 is a schematic diagram showing a user
`application and a STREAM, in accordance with embodi
`ments of the present invention.
`0045 FIG. 26 is a high-level diagram of a file system, a
`Swap device, physical memory, and the structures used to
`transfer data between them.
`0046 FIG. 27 is a diagram of a page structure, used in a
`virtual memory system.
`0047 FIG. 28 is a diagram of a user process, a VM sub
`system, a file Subsystem, and disk.
`0048 FIG.29 is a diagram of the steps used to encryptand
`decrypt pages in accordance with the present invention.
`0049 FIG. 30 is a high-level diagram of a data encryption
`algorithm in accordance with the present invention.
`0050 FIG. 31 is a low-level diagram of a data encryption
`algorithm in accordance with the present invention.
`
`DETAILED DESCRIPTION OF THE INVENTION
`0051. In the following description, identical numbers indi
`cate identical elements. Where an element has been described
`in one Figure, and is unaltered in detail or relation in any other
`Figure, said element description applies to all Figures.
`0.052 The present invention, termed an Encrypting Oper
`ating System (EOS), is a modified UNIX operating system.
`The EOS is not restricted in operation to a particular UNIX
`operating system, although its preferred embodiment is based
`on the architecture of the AT&T UNIX SVR3.4, SVR4,
`SVR4.2, and SVR5 operating system kernel. For purposes of
`clarity and consistency, the following description will be
`restricted to the description of an EOS that is a modified
`AT&T UNIX SVR4 operating system kernel, but it should be
`understood that it is within the scope of the present invention
`to produce the EOS by modifying other UNIX operating
`systems.
`0053 Preferably, the EOS is part of a micro-kernel, such
`as those found in UNIX System V configurations, including
`Sun Microsystems Solaris (SVR4.0), Silicon Graphics, Inc.,
`IRIX (SVR4.0), IBM's AIX (SVR3.4), Hewlett Packard’s
`HP-UX (SVR3.4), and Santa Cruz Operations’ UNIXWare 7
`(SVR5), and later version of each, to name a few. It will be
`appreciated, however, that embodiments of the present inven
`tion can also be used with monolithic kernels, such as Linux
`and BSD.
`0054 The EOS's modifications enable it to encrypt and
`decrypt both the contents and the names of any data it is
`managing or storing. The EOS can selectively e