Transcript Slides

Undetectable Stegosystem
Based on Noisy Channels
V. Korzhik, G. Morales Luna, K. Loban
Singapor, NTU, 2010
1
1. Introduction
Steganography (SG) is the information hiding technique that embeds the hidden
information into an innocent cover message (CM) under the conditions that the CM is not
corrupted significantly and that the presence of the additional information into the CM may
not be detected.
Basic principle
of undetectability:
The CM and the SG signal have to be indistinguishable even with
the use of the best statistical methods.
2
Designer’s problem:
He (or She) should know the full statistics of the CM, but it is a
rather very hard to study completely the probability distribution of
such CM as video or audio signals.
In order to be successful within this risky situation (which is, indeed, a “bottleneck” of
any SG system) we propose to move into another concept of SG system setting, namely to
SG based on noisy channels.
This setting can be justified if there exists in a natural manner a noisy channel and the
attacker (“stegobreaker”) is able to receive the stegosignal just over this channel and
nothing else.
3
Attacker’s problem:
To distinguish statistically the CM after its passing over the noisy
channel and SG signal passing over the same noisy channel.
Reducing of the steganalysis problem:
Recognition of channel noise and the sum of the
channel noise and the embedded signal.
Since the channel noise distribution is, as a rule, known much better than the CM
distribution, the problem to design SG systems which are resistant to their detection is
simplified.
New assumption: CM can be publicized; such assumption is impossible for
conventional SG, because otherwise they can be detected trivially – if
SG ≠ CM, then something has been embedded.
4
Model of SG design for a Gaussian noisy channel:
 n  1, 2,..., N
Cw (n)  C (n)  (1)b  w (n),
(1)
where C   C (n) n 1 are the samples of CM,
N
   (n) n 1 is a zero mean Gaussian pseudorandom i.i.d. reference sequence with variance 1,
N
N  is the lenght of both sequences,
 w  is the depth of embedding
After a passing of the watermarked signal through the Gaussian channel we get:
Cw (n)  Cw (n)   (n),
 n  1, 2,..., N
(2)
where     (n) n 1 is a zero mean Gaussian i.i.d. noise sequence with variance  2
N
5
More early results [1] for the case when an attacker knows CM:
 
1 
1 
D  0.72 N ln 1    1  w  
  w 

(3)
Where D is the relative entropy (introduced in [2] as a measure of SG system
security, w   2  w2
Approximation of D for large w:
D  0.36 N2
(4)
w
It is well known from Information Theory [2] the following inequality for any hypothesis
testing:
P
1 Pfa
Pfa log fa  (1 Pfa )log
 D,
(5)
Pm
1 Pm
where Pfa is the probability of SG signal false alarm,
Pm is the probability of signal missing
SG system is secure (or ideal) if D  0 and then Pfa  Pm  1 2 that is equivalenty to random
guessing of SG system presence or absence.
If we let Pfa  Pm  P then by (5) we get
 2P 1 ln 1PP  D
From eq. (4) it follows that
w  0.6
N
D
(6)
(7)
6
Legal informed decoder (C (n) is known):
N
0 if   0

   (Cw (n)  C (n)) (n)  b  
n 1
1 otherwise
(8)
The bit error probability [1]:



N 
N
Pe  Q 

exp






2
2


2


w
w





(9)
2
t
1
where Q : x  Q( x) 
e 2 dt

2 x
The general relation that comprises both security and reliability [1]:

( ND)1 4
Pe  Q 1.29
m1 2



( ND)1 2 
  exp  0.83

m



(10)
where m  N N 0 is the number of secure embedded bits into N samples.
7
Optimistic draw:
For any security level D and the number of secure bits m there can
be chosen an appropriated N such that the SG system provides any
given reliability Pe.
Pessimistic draw:
The more is N for given D the less (see eq.(7)) should be “signal-to1
2
2
noise” ratio w   w   and this results in a problem for practical
implementation (especially for digital processing).
Example.
Let D=0.1 (that provides an acceptable level of security) and let m=10 be
the number of the secure embedded bits
4
If we choose N  105 , then Pe  2.5  10 by (10) which is acceptable. But
 c2
w  600 by (7) and if the CM signal-to-noise ratio 2  102

 2
N
4
2
where  c  var  C(n) n 1 , then
 6  10 which is indeed unacceptable.
 w2
.
.

Our proposal:

To use so called spread-time stegosystem (STS) – see next Section.
8
2. Description of STS and its performance evolution.
2.1. Uncoded system.
Pr[Cw (n)  C (n)  (1)b  w (n)]  P0
Pr[Cw (n)  C (n)]  1  P0
Practical implementation:
, n  1,2,...N
(11)
Let  nm m1 be an increasing sequence of indexes, N S  N
generated by a secret stegokey K, determining the samples in
which the WM’s are to be embedded (see Fig.1.) Then for a large
value of N we may assume that P0  N S N .
NS
Fig.1. STS system with embedding into pseudorandom samples.
( Here N s  8, N  38, P0  8 38).
In order to embed one secret bit b are used N 0 consecutive chosen samples.
Hence the total number of secret bits embedded into N S samples is N t  N S N 0
9
Legal user knows the stegokey K, hence he knows exactly the samples with embedding and
can execute the decision rule (8).
The error probability can be found by (9).
Optimal STS detecting by an attacker:
The two hypothesis have to be tested:
H 0 : [  (0,  2 ) and it is an i.i.d.]
2

 with the probability P0 :[ (0,  s ) and it is an i.i.d.]
H1 : 
2
with
the
probability
1

P
:[


(0,

) and it is an i.i.d.]



0


(12)
where    (n)   Cw (n)  C (n) n 1 ,
N
 s2   2   w2
10
The optimal hypothesis testing based on maximum livelihood ratio [3] is
 (1 0 )    H1 ; (1 0 )    H 0 
(13)
N 

  w2
 2
P( H1 )
2
where (1  0 ) 
   P0
exp  2 2  (n)   (1  P0 ) 
2


P( H 0 ) i 1 
s
 2 s  


By changing the threshold  in (13) it is possible to pass to the logarithmic livelihood ratio:


  w2
 2
2
 L (1  0 )   log  P0
exp  2 2  (n)   (1  P0 ) 
2
(14)



2


n 1
s
s





2
2
Let us assume that  w   (for a good security guarantee), then we get from (14) after
simple normalization.
N


 1
1 N
2
 L (1  0 )   log  P0 exp  2 2  (n)   (1  P0 ) 
N n1
 2w 



(15)
11
The series expansion of x  exp( x) up to its linear term and next the series expansion of
x  exp( x) up to its linear term renders the following decision rule:
.
     H1  ;      H 0 

 

1 N 2
where     n ,   is some new threshold
N n 1
(16)
Let us estimate (using the Central Limit Theorem) the missing and false alarm probabilities,
Pm and Pfa , respectively:

 ( x  m1 ) 2 
Pm 
exp  
 dx
2
2 
2 0 
2 0 

1
Pfa 

1
2
(17)
2
0
 ( x  m0 ) 2 
 exp   2 02  dx
(18)
where m j   [ H j ],  2j  var( H j ) for j  0,1
12
Let us select (for simplicity) the threshold  in such away to be Pm =Pfa =P,
Then after simple transforms of eq’s (17)-(18) we get
 m  m0 
P  Q 1

2

0


where m0   2 , m1   2  P0 w2 ,  02  2 4 N
(19)
(20)
Substituting (20) into (19) we obtain:
 N P0 


NS
P  Q
  Q

2
2

2
2
N


w 
w 


If N S
(21)
N , then P 1 2 and an undetectable stegosystem results.
In Table 1 we show the calculation results for some values of parameters: N S , N 0 , m, P0
providing Pe  103 , P  0.4 given the same values of N and  w .
13
Table 1. Sets of parameters for STS providing Pe  103 , P  0.4
given different values N and w .
N
10 4
105
106
107
w
N0
NS
m
P0  N S N
20
210
1431
6
0.1431
50
496
3578
7
0.3578
100
973
7156
7
0.7156
20
210
4526
21
0.04526
50
496
11310
22
0.1131
100
973
22630
23
0.2263
20
210
14310
68
0.01431
50
496
35780
72
0.03578
100
973
71560
73
0.07156
20
210
45260
215
0.004526
50
496
113100
228
0.01131
100
973
226300
232
0.02263
We can see that for large enough N it is possible to provide a good undetectability ( P0  0.4) and
reliability ( Pe  103 ) of STS and embed up to 232 secure bits.
14
2.2. Coded system.
We restrict our attention to binary linear systematic
( N 0 , k , d )  codes.
Embedding:
Pr[Cw (n j )  C (n j )  (1) ij  w (n j )],
b
(22)
where n j is the sample index with embedding.
Decoding:
N0
i  arg maxk   Cw (n)  C (n)  (1)bin  (n)
1i  2
n 1
(23)
where bin is the n-th bit in the i -th codeword of length N 0  N S l with l a positive integer value.
Total number of secure embedded bits is m  k  l.
The block-error probability based on union bound [5]:



d 
d
Pbe   2  1 Q 
 RN 0 ln 2 
  exp  


2
2


2


w
 w



where R  k N 0  the code rate.
k
(24)
15
Since signal-to-noise ratio w1 is typically small, we will restrict our consideration only to two
classes of linear error correcting codes:
The simplex codes (SC):
N0  2  1, k   , d  2 1, R   N0 , where  is some integer
v
The Reed-Muller codes (RMC): N 0  2 , k    , d  2 r , where   3 and r -is integer, the so

r
i 
called order of the RMC.
i 1
Example:
SC :
N  107 , P  0.4, w  20, N S  45257.
the optimal parameters:   10, k  10, Pbe  103 , m  k 
NS
 442
N0
RMC : the optimal parameters:   14, r  2, k  105, Pbe  109 , m  290.
16
3. Optimal SG system detecting rule.
Let us verify if the use of the optimal decision rule (15) can provide an appreciable
improvement of STS detecting in comparison with the suboptimal decision rule (16)?
Since N is sufficiently large, we can apply the Central Limit Theorem [4] to the sum in (15).
Similar to the proof of (19) we get for such a choice of threshold  , which provides Pm =Pfa =P :
where, for j  0,1:
 m1  m0 
P  Q

2

0


N
2
 


 ( n)
m j  E log  P0 exp
 (1  P0 ) 
Hj
2
2



w

n1
 

2


2
2










1
1
 ( n)
 ( n)
2
2
 0  Var log  P0 exp
 (1  P0 )  H j  
E  log  P0 exp
 (1  P0 )  H 0    m0
2
2
2 w   
2 w   

N


 
 N   
 

where random values  (n) have the probability distributions by (12)
17
Since it is very hard to find analytically the values m0 , m1 and  0 , we estimate them by the simulation:
N
 2
1
4
10
5
1
5
10
5
1
6
10
5
w
P0  NS N
m0
m1
0
 m  m0 
P  Q 1

 2 0 
20
0.1431
0.00161414
0.00162667
0.00240398
0.401753
50
0.3578
0.00157674
0.00158801
0.00229017
0.401759
100
0.7156
0.00156462
0.00157585
0.00225445
0.401737
20
0.1431
0.00161414
0.00162590
0.00240398
0.401754
50
0.3578
0.00157675
0.00158821
0.00229017
0.401745
100
0.7156
0.00156462
0.00157583
0.00225445
0.401726
20
0.04526
0.000512618
0.000513737
0.000767001
0.401741
50
0.1131
0.000500332
0.000501449
0.000729712
0.401809
100
0.2263
0.000496672
0.000497830
0.000718483
0.401737
20
0.04526
0.000512618
0.000513854
0.000767001
0.401772
50
0.1131
0.000499062
0.000500277
0.000727769
0.401806
100
0.2263
0.000496672
0.000497795
0.000718483
0.401745
20
0.01431
0.000162288
0.000162393
0.000243341
0.401835
50
0.03578
0.000158479
0.000158585
0.000231440
0.401862
100
0.07156
0.000157686
0.000157808
0.000228397
0.401548
20
0.01431
0.000162288
0.000162435
0.000243187
0.401752
50
0.03578
0.000158479
0.000158598
0.00023144
0.401711
100
0.07156
0.000157686
0.000157797
0.000228397
0.401461
We can see that the use of the optimal decision rule does not break undetectability of STS.
18
4. Simulation of STS for audio cover messages.
We use audio music file with duration about 29 sec in format wav where the sampling
frequency is 44.1 kHz.
The CM signal-to-noise ratio c  10 dB , whereas watermark-to-noise ratio (WNR) w1  20 dB
The embedding rule was taken by (11), where P0  0.1.
In Fig. 2 the wave forms of original audio signal, audio signal after passing over a noisy channel
and after secret message embedding at the same time interval are presented.
One can see that noise corrupts slightly the audio signal and this fact can also be appreciated by
human ear, whilist, at the same time, the embedding procedure is not observable by human ear.
19
Fig.2. The waveforms of audio signal (a), audio signal after its passing over noisy channel with
CM signal-to-noise ratioc 10dB(b), and after embedding by STS algorithm with WNR  20
dB(c)
20
In Fig.3 the waveforms of channel noise are shown, as well as this noise after embedding.
Fig.3. The waveform of channel noise (a) and
the same channel noise after embedding (b).
In Table 3 we present the results of simulation for the error probability Pe versus
the parameters N0 and w . Pe is the theorical error probability.
w
N0
20
210
5 10 4
0.001
50
496
6 104
0.001
100
973
5.5 104
0.001
Pe
Pe
21
5. Conclusion.
1. Some modification of the stegosystem based on noisy channel called spread-time stegosystem
(STS) has been proposed.
2. Both STS security and reliability can be provided by an appropriate selection of the system
parameters.
3. The main defect of STS is its low embedding rate. The use of error correcting codes improve
this situation but only slightly.
4. The suboptimal system detection by (16) is practically as much efficient as the optimal
by (15).
5. Simulation of the STS with audio CM shows that its detection by ear and eye is impossible,
whereas the embedded bits can be extracted reliably.
22
Open problems.
1. To specify security of STS for digital CM and after a saving the stegosignal in digital formats.
2. Consider applications of STS in real noisy channels (including optical fiber channels).
3. An extraction of secret bits by a “blind” decoder (see [6]) while keeping a good
undetectability of STS.
4. Investigation of attack to prevent an extraction of secure embedded bits (additive noise,
compression/decompression, resynchronization ).
5. Improvement of coded STS (farther optimization of codes and decoding algorithms).
23
References.
[1] Valery Korzhik, Moon Ho Lee, Gullermo Morales Luna, “Stegosystem Based on Noisy
Channels”, Trans. VII Spanish Meeting on Cryptography and Information Security, 2006;
[2] Cachin C., “An information theoretic model for stegonography”. In: International workshop
on IH, 1998, pp. 306-318.
[3] Van Der Warden, “Mathematische Statistik”, Springer-Verlag, 1957.
[4] Papoulis, A. “Pobability, Random Variables, and Stochastic Processes”, McGraw-Hill, NewYork, 1984.
[5] MacWilliams, F. Sloan, N. “The Theory of Error Correcting Codes”. Bell Labs, 1991.
[6] Malvar, H.S. Florencio, D. “Improved spread spectrum: A new modulation technique for
robust watermarking”. IEEE Transaction on Signal Processing 51 (2003), pp. 898-905/
[7] Valery Korzhik, Guillermo Morales-Luna, Ksenia Loban, “Undetectable Spread-time
Stegosystem Based on Noisy Channels”. Submitted for journal “Information Hiding”, Lecture
Notes in Computer Science, 2009
24