13 An Application of Secret Sharing Scheme to UNIX File System 1020290 15 2002 2 Scheme) SSS SSS SSS SSS UNIX (SSS: Secret Sharing UNIX ssar ssar / UNIX
An Application of Secret Sharing Scheme to UNIX File System SAWANO Mitsuharu SSS (Secret Sharing Scheme) is a method to data storages to have disaster prevent property and secarity. There is a command named ssar implemented on UNIX. The command has a problem that user must be conscious of SSS. The purpose of this research shows a method for file storage that users are not conscious of SSS. I made proposal of the application of SSS to UNIX File System. I created the encrypt/decrypt module that necessary to implementation of SSS. key words Secret Sharing Scheme, disaster prevention property, Security, UNIX File System
4.3.3 . . 22 5 / 24 5.1 24
24 5.1.2 26 5.2 27
27
6 29 6.1
29 6.2 29 31 32 A / 33
33
34
4.1 Null 18 1 (Secret Sharing Scheme) SSS SSS UNIX ssar ssar SSS SSS SSS UNIX / 2 3 UNIX UNIX 4 5 / 6 2 Shamir (k, n) SSS ssar
2.1
(SSS: Secret Sharing Scheme) 1979 Blakley[1] Shamir[5] Shamir (k, n) SSS 2.1 2.2 2.1.1 (k, n) SSS 1 SSS (k, n) SSS n ( 2.1) k – 1 k: ( 2.2) [7, 10] 2.1.2
SSS [9] SSS k – 1 f(x) S' (xi, f(xi)) = (xi, wi) Wi GF(p) (p
p – 1 1 ID . 1. GF(p) 0 n x i (i = 1, 2, . . . , n ) 2. i = 1,2,...,n X i H i .
r j (j = 1, 2, . . . , k − 1) 2. wi = f(xi)
(2.1) 3. wi ID k: S Xi Wi
f (x) k: S, r 1 , r 2 , . . . , r k − 1 k: S + r1xi1 + r2xi1 + . . + rk-1xi1 k-1 = wi1 S + r1xi2 + r2xi2 + . . . + rk-1xi2k-1 = wi2 S + r1xik + r2xik + . . + rk-1xik k-1 = wik

– 5 –
1
1 1
Wi1
S . 1. k Xiz . 1. Xij Wij (mod 7) f(x) = S + r1x + r2x2 + Tk-1 Xk-1 k: 2. 1 3. k 4. S k:
2.1 y = f(x) S y k – 1 2.1 k wi (i = 1, 2, . . . , n )たy = f(x) k – 1 y S k — 1 : 1 p =7, k =3, n =5
G
( ID , x 1, x 2, . . . , x 5      x 1 = 3, x 2 = 2, x 3 = 6, x 4 = 4, x 5 = 5 w1 = 1, w3 = 3, w4 = 2 H 1 , H 3 , H 4 f(x) f(x) = S + r 1x + r 2x 2 ID f(x1), f(x3), f(x4) (x 1 , w 1 ) = (3, 1), (x 3 , w 3 ) = (6, 3), (x 4 , w 4 ) = H 1 (4, 2) x1 = 3 f (3) = $ + 3r1 + 32r1 = 1
S = 3
2.2
SSS
SSS Shamir (k, n) ssar (Secret Sharing ARchiver) [8] ssar UNIX
ssar -c -s number -t number -b number -f basename sourcefilename -C -ニ-t -f basename -b ssar -x -f decodefilename sharefilename1 sharefilename2 ... -X -f 3
UNIX 4 SSS UNIX UNIX
3.1
UNIX
UNIX BSD Solaris UNIX 1 1 i (index node) i UNIX i OS ISO9660 i SSS (Virtual File System)   i VFS 3.1 v (virtual node)
3.2

4.4BSD
3.2
Null 3.2
Null
3.2.1
Null [4] 2 Null mount_null mount_null 2 (target-pn) (mount-point-pn) 1 Null Null (target-pn) mount_null (mount-point-pn) mount_null [-o options] target mount_point -O ● async ) 1 3.2 I/O ● force ● sync I/O ● rdonly ● noexec mount_null 3.3 mount_null /usr/src /home/guest/src 3.4 /usr/src /home/guest
Null
3.2.2
Null Null 3.5 v v null-node v null-node v v null-node 4 SSS SSS /
Secret Sharing File System
4.1
SSS Shamir (k,n) ssar (Secret Sharing ARchiver) ssar
) SSS UNIX ssar ssar SSS SSS UNIX SSS SSS UNIX SSS SSS 4.2 SSFS SSS UNIX SSFS (Secret Sharing File System) 4.2 SSFS UNIX UNIX / 4.2.1 / Null Null SSS UNIX SSS 2 SSFS 2 write/read Null SSS (k,n) SSS UNIX write/read SSFS SSFS Null Null SSFS 4.1 / / / /
4.2.2
1. 2. 3. 3 Null 4.1 4.1 Null 4.2 SSFS
: : × 4.1 null_bypass Null null_bypass / 1 SSS UNIX SSS Null mount/umount / / 4.3 / / 3 SSS / SSS (2, 3) 1 SSFS 4.3 / SSS / (     ??     ) 4.3.1 C / char 9 int SSS 4.3 / 1 3 9 int 4 3 3 (1,3),(2,3),(3,3) (3, 3) (1,3) 3 1 (2,3) SSS Shamir 257 257 3 1 4.3.2 char 1 int 4 3 27 3～5 1 4 5 2 4.2 4 byte L 4.2 4.3.3 int 4 2 3 3 / 1 2 1 2 1 1 0 1 4.3 4.4 4.3 ( ) 4 byte 4.4 ( ) 3 3 5 / / 5.1 / / 5.1.1 / test.txt test.txt 0x00 0xFF testout cmp test.txt / 5.1 5.1 1 5.2 5.1 1
5.2
2 f7 16 fa 100 11 1
00
1 00 e5
3 00 f7 fd  e5 test.txt test2.txt 5.1.2 2 2 (2,3) SSS 1.
2 2.
3. 2 3 3 cmp test2.txt 1 test2out2 3 test2out1 test2out3 2 2 1 fd 5.3 1 1 5.3 
 
 5.2 / 5.2.1 0 1 0 1 3 2
5.4 ssfs_decode23_error 6. 2 7. 3 8. 8 ssfs_decode23 error! 1 4 5 8 5.4 1 2 0 1 6 6.1 SSS UNIX SSS / SSS 6.2 Null UNIX SSS 1 / / 1 / SSS UNIX / SSS UNIX Null write/read / Null mount SSFS 6.2 [1] G.R Blakley. Safeguarding cryptographic keys. Proc. of AFIPS 1979 Nat. Computer Conf., Vol. 48, pp. 313–317, 1979. [2] John Shelby Hedemann. Stackable layers: An architecture for file system develop- ment, Aug 1991. [3] John Shelby Hedemann and Gerald J.Popek. File system development with stack- able layers, Jul 1993. [4] Jan-Simon Pendry and M.K.McKusick. Union mounts in 4.4bsd-lite, Jan 1995. Conference Proceedings of the USENIX 1995 Technical Conference on UNIX and Advanced Computing Systems. [5] A. Shamir. How to share a secret. Communication of the ACM , Vol. 22, No. 11, pp. 612–613, 1979. [6] Uresh Vahalia. UNIX , pp. 421–426. May 2000. [7] , , June 1997. [8] [9]
[10]
, 2001. pp. 1228–1236, Dec 1999.

A.1
1 #define RANDOM 1  /* */ 2 #define PRIME 257 /* */ 3 4 int ssfs_encode23(char secret){ 5 6 int w1,w2,w3; 7 int result = 0; 8 int G [3][3] = { 9 1,3,9, 10 1,9,81, 11 1,27,729 12 } ; 13 /* 1 */ 14 w1 = (G[0][0]*secret + G[0][1]*RANDOM) % PRIME; 15 /* 2 */ 16 w2 = (G[1][0]*secret + G[1][1]*RANDOM) % PRIME; 17 /* 3 */ 18 w3 = (G[2][0]*secret + G[2][1]*RANDOM) % PRIME; 19 20 /*1 */ 21 result = (result & 0x00fffff) | (0x07 << 24); 22 /*2 1 */ 23 result = (result & Oxff00ffff) | (w1 << 16); 24 /*3 2 */ 25 result = (result & Oxfff00ff) | (ជ2 << 8); 26 /*4 3 */ 27 result = (result & Oxfffff00) | w3; 28 29 return result; 30 31 } 32
A.2
1 */ #define PRIME 257 /* 2   int ssfs_decode23(int share){ 4 5 int check; 6 int w1,w2,w3; 7 int result=0; 8 int G1 [2][2] = { 9 387,-129, -43,43 10 } ; 11 12 int G2 [2][2] = { 13 19320201,-2146689, 14 -715563,715563 15 } ; 16 17 int G3 [2][2] = { 18 387,-129, 19 -3698,3698 20 } ; 21 22 /* 23 */ check =  (share & Oxff00000) >> 24; 24 25 /* 1 w1 = 26 27 /* w2 = 28 29 /* (share & 0x00000ff); w3 = 30 31 switch(check){ 32 case 0x06: 33 result = (w1 *G1[0][0] + G1[0][1] * w2) % PRIME; 34 result = (result & 0x00fffff) | (0x07 << 24); 35 */ (share & 0x00ff000) >> 16; 2 */ (share & 0x000ff00) >> 8; 3 */ – 35 – 36 break; 37 case 0x05: 38 result = (w1 *G2[0][0] + G2[0][1] * w3) % PRIME; 39 result = (result & 0x00fffff) | (0x07 << 24); 40 break; 41 case 0x03: 42 result = (w2 *G3[0][0] + G3[0][1] * w3) % PRIME; 43 result = (result & 0x00fffff) | (0x07 << 24); 44 break; 45 case 0x07: 46 result = (w1 *G1[0][0] + G1[0][1] * w2) % PRIME; 47 result = (result & 0x00fffff) | (0x07 << 24); break; 48 default: 49 break; 50 → 51 52 53 return  result; 54 55 }