19-06-2014, 02:26 PM
Enhancing Data Trustworthiness
via Assured Digital Signing
[attachment=65063]
Abstract—Digital signatures are an important mechanism for ensuring data trustworthiness via source authenticity, integrity, and
source nonrepudiation. However, their trustworthiness guarantee can be subverted in the real world by sophisticated attacks, which
can obtain cryptographically legitimate digital signatures without actually compromising the private signing key. This problem cannot be
adequately addressed by a purely cryptographic approach, by the revocation mechanism of Public Key Infrastructure (PKI) because it
may take a long time to detect the compromise, or by using tamper-resistant hardware because the attacker does not need to
compromise the hardware. This problem will become increasingly more important and evident because of stealthy malware (or
Advanced Persistent Threats). In this paper, we propose a novel solution, dubbed Assured Digital Signing (ADS), to enhancing the
data trustworthiness vouched by digital signatures. In order to minimize the modifications to the Trusted Computing Base (TCB), ADS
simultaneously takes advantage of trusted computing and virtualization technologies. Specifically, ADS allows a signature verifier to
examine not only a signature’s cryptographic validity but also its system security validity that the private signing key and the signing
function are secure, despite the powerful attack that the signing application program and the general-purpose Operating System (OS)
kernel are malicious. The modular design of ADS makes it application-transparent (i.e., no need to modify the application source code
in order to deploy it) and almost hypervisor-independent (i.e., it can be implemented with any Type I hypervisor). To demonstrate the
feasibility of ADS, we report the implementation and analysis of an Xen-based ADS system.
INTRODUCTION
DIGITAL signatures are an important tool for ensuring
data trustworthiness. The cryptographic assurance of
digital signatures is well understood [1], assuming the
private signing keys are not compromised (despite sidechannel
attacks [2]). An appreciated problem is to attain a
stronger signature trustworthiness than the cryptographic
assurance. However, existing solutions to this problem are
not sufficient. Specifically, the cryptographic approach—including
digital signatures of various flavors: threshold
signature [3], proactive signatures [4], forward-secure
signature [5], [6], key-insulated signature [7], and intrusion-
resilient signatures [8]—can mitigate, but cannot prevent,
the compromise of signature trustworthiness. PKI-like
key revocation mechanisms are not sufficient because the
compromise may not be detected until after a long time. It is
also not sufficient to put the private signing keys in tamperresistant
hardware devices [9]. This is because the attacker
can compromise the signing functions without compromising
the private signing keys and without compromising the
hardware devices; for example, the attacker uses stealthy
malware to penetrate into the Operating System (OS) kernel
and then asks the device to sign the attacker’s messages [10],
[11]. In order to enhance signature trustworthiness in the
real world, we need to address such powerful attacks.
Our contributions. We propose enhancing data trustworthiness
via Assured Digital Signing (ADS), which allows a
signature verifier to examine not only digital signatures’
cryptographic validity as in the current daily routine
practice, but also their system security validity that the
private signing keys and the signing functions are secure. In
particular, ADS deals with the powerful attacks that the
signing application program itself may be malicious (e.g., a
backdoor was embedded by its vendor or developer), and
that the underlying general-purpose OS kernel is malicious.
In order to minimize the modifications to the Trusted
Computing Base (TCB), we propose a modular design of
ADS, which simultaneously takes advantage of trusted
computing and virtualization technologies.
We show that ADS can enhance digital signatures’
trustworthiness against the powerful attacks, as long as
(essentially) the hypervisor is secure. Although this assumption
is accepted by some researchers, it is deemed as
somewhat strong by others. We believe that hypervisors
will become significantly more secure in the near future (cf.
[12], [13], [14], [15], [16]). The modular design of ADS makes
it application-transparent because there is no need to modify
the application source code in order to deploy it, and almost
hypervisor-independent because it can be implemented on
any Type I hypervisor. The modular security analysis, albeit
informal, shows that if certain component properties are
MODULAR DESIGN AND SECURITY OF ADS
Now, we present the modular design of ADS.We argue that
ADS attains the desired security properties based on that
certain abstract component properties can be satisfied.
2.1 Design Requirements
The design requirements of ADS are: First, it should enhance
the trustworthiness of digital signatures by allowing a
signature verifier to examine not only the digital signatures’
cryptographic validity but also their security validity that
the private signing key and the signing function are secure.
This naturally suggests using some form of attestation.
Second, it should minimize the changes (if inevitable) to the
TCB. Third, it should be applicable to most, if not all, system
software platforms (i.e., platform independence) and should
not force modification of the application source code in
order to deploy it (i.e., application transparency).
The threat model consists of two attacks:
The Secure Communication Channel
Component
We propose using Xen’s shared memory mechanism to attain
the secure communication channel between the signing
application and the signing server. The reason for choosing
this mechanism, rather than the memory copy mechanism, is
not only that we can simplify the control over the protected
content (i.e., one copy in the case of memory mapping
versus multiple copies in the case of memory copy), but also
that memory mapping is more efficient especially when the
messages to be signed are in large volume.
As illustrated in Fig. 5, four physical memory regions,M0-
M3, are used as shared memory. SinceM0-M3 are mapped to
the user-VM, we need to protect them by making the
following changes to the page table entries (PTE) corresponding
to M0-M3. Specifically,
The Attestation Component
In order to measure the integrity of the signing application in
the user-VM, we need to know what comprises the
executable without relying on the user-VM kernel. Recall
that we measure the hash of application the executable and
the libraries (including the shared ones) the application
program calls, which exploits that in x86’s 32-bit PAE mode,
all code-segment pages are marked as “NX ¼¼ 0” if and
only if they are executable. When the signing application
program uses the call gate to request for signing service, the
DAI ET AL.: ENHANCING DATA TRUSTWORTHINESS VIA ASSURED DIGITAL SIGNING 843
Fig. 5. Highlight of the “shared memory”-based implementation of
secure communication channel. There are four physical memory
regions, M0-M3, with each of size 256 KBytes (which can be set as a
system parameter when installing ADS). M0 and M1 are mapped to the
user-VM’s kernel space for the security monitor itself, M2 and M3 are
mapped to the user-VM’s user space for the signing application, andM1,
M2, and M3 are mapped to the trusted-VM’s user space for the signing
server.M0 stores the code of the security monitor,M1 stores information
for attestation, M2 stores the message, and M3 stores the signature.
1. There is no practical way, if feasible at all, for the hypervisor to ensure
the integrity of the kernel module because the kernel module can make
many system calls, which can be compromised by the kernel.
hypervisor will compute the hash value of the application
program’s executable pages, write the hash value inM1, and
notify the policy engine. The policy engine compares this
measurement against the hash value of the application
program stored in the trusted-VM, which may be provided
by the software vendor or simply computed by the user at a
clean system state. If they match, the policy engine extends
this measurement into TPM’s PCR 9 for later attestation
purpose; otherwise, it prompts the user that the application
program in the user-VM has been corrupted. After the user
allows the signing request and the signing server generates a
digital signature, the signing server measures the hash value
of the message and the signature, and extends the hash value
to TPM’s PCR 11. Then, TPM’s standard attestation is
extended to accommodate PCR 9 and PCR 11, which allows
the signature verifier to examine the signing application, the
message and the signature. Note that all the hash values are
computed using SHA-256.
For applications that require to sign multiple signatures,
we propose the following cache-like performance enhancement.
Specifically, we allow the signing application to
request multiple signatures while amortizing the cost of
measuring the signing application program’s memory pages.
This can be achieved by locking the application program’s
executable pages so as to prevent the Time-of-Computing-to-
Time-of-Use (TOCTOU ) attack that can tamper the binary
after the measurement. As a result, the hypervisor only needs
to compute the hash value of the application program once
for signing multiple messages.
It is worthwhile to point out that if needed (e.g., when
ADS is used as a component in larger system), the attestation
service can be further extended to incorporate, for example,
the system call table and the Interrupt Descriptor Table (IDT)
in the user-VM. These tables do not change unless the kernel
is re-compiled and are often modified by attacks, which
means that this would allow detecting some attacks. If the
signing application needs to modify the Page Table Entries, it
can invoke call_gate(3,0) to unlock the memory. When the
signing application needs to use the signing service the next
time, it can invoke call_gate(1,0) to lock and measure the
executable pages again.
Performance Evaluation
The performance of the Xen-based ADS is mainly influenced
by three major factors: the time spent on the inter-VM
communication, the time spent on the digital signing, and
the time spent on attestation. In order to see which part is
the most time consuming, We first measure the time spent
on the inter-VM communication, then the ADS response
time but without attestation, finally the ADS response time
with attestation.
All experiments are performed on an HP xw4550 workstation,
with a quad-core 2.3 GHz AMD Opteron processor
and 4 GBytes of RAM. The machine has a v1.2 Broadcom
TPM, revision level A2. The software environment for all
experiments is paravirtualized Xen 3.3.1 installed on Ubuntu
8.04 LTS with the 2.6.18.8-xen kernel. The user-VM runs the
same paravirtualized kernel that is provided with Xen 3.3
and we give the Domain U 512MRAM and one virtual CPU
core. For the signing server, we use Peter Gutmann’s
cryptlib library version 3.3.3. We use PKCS#7 CMS
signing with RSA + SHA hash. The RSA key size was the
cryptlib default (2,048 bits).
Fig. 8a plots the inter-VM communication time with
varying size of messages, including the cost for protecting
M2. Each data point is averaged based on the 100,000
messages of the same size. We observe that for messages
with size up to 500 KBytes, the time is linearly related to
the message size; for messages with size exceeding
500 KBytes, the time is still linearly related to the message
size but with a smaller factor. This phenomenon is likely
that the AMD Opteron processor has 4 512 KBytes
L2 Cache, and the CPU optimization will give priority to
large (greater than 512 KBytes) and consecutive memory
access, which would occur in our experiment.
Fig. 8b plots the response time of ADS but without
attestation, where each point in the graph is averaged over
500 runs. For comparison purpose, it also plots the signing
cost with local cryptography library. We observe that the
differential is steadily about 0.01 seconds, which accommodates
the 0-0.006 seconds depicted in Fig. 8a, the time spent
on computing the hash value of the signing application, the
time spent on mapping the shared memory regions, and the
time spent on unmapping the shared memory regions after
obtaining the signature.
Fig. 8c plots ADS’s response time with TPM-based
attestation, where each point in the graph is averaged over
500 runs. For comparison purpose, it also plots ADS’
response time without attestation. We observe that there is
a large performance difference (about 5 seconds) between
using attestation and not using attestation. This is caused by
the underlying attestation technique and specific to the TPM
hardware platform in our experimental system. Specifically,
the noticeable cost is due to the TPM quote operation for
attestation, which is essentially for computing a 2,048-bit
RSA signature on the relevant PCR values, which takes about
5 seconds on the TPM’s low-end/cheap processor.
In summary, the inter-VM communication mechanism is
indeed very efficient, which justifies our design choice of
using the shared memory mechanism for this purpose. The
phenomenon that ADS’ response time is reasonably flat with
respect to varying size of messages is caused by 1) the inter-
VM communication mechanism is very efficient and only
consumes a very small portion of the response time, and
2) the TPM-specific attestation service consumes most part of
ADS’ response time but is independent of the size of the
messages because the attestation is always on the fixed-size
PCR values. We believe that the computational cost of TPMbased
attestation is not as significant as the security gain
implied by not causing many modifications to the hypervisor
(which would offer better performance). Moreover, any
performance improvement in TPM’s attestation service will
directly benefit ADS.
CONCLUSION
Enhancing signature trustworthiness is of fundamental
importance. We have presented a novel solution to this
problem, while dealing with malicious signing application
and/or malicious general-purpose OS kernel. To demonstrate
its feasibility, we reported a Xen-based implementation
and discussed the implementation issues on other Type I
hypervisor platforms.
Future research directions. There are opportunities for
future research. First, it is important to reduce, if not
eliminate, the reliance on the user to confirm that a message
signing operation was indeed initiated by a human user.
Second, we observe that the user confirmation mechanism
offers enhanced source nonrepudiation, which could be
exploited to hold insiders (i.e., corrupt authorized users)
more accountable. This is because they cannot attribute
signatures to the attacks we addressed. As such, it is
interesting to characterize to what extent accountability can
be gained by deploying ADS. Third, it would be very
interesting to formalize the type of (modular) security
analysis we conducted. It appears that both the cryptographic
framework and the Dolev-Yao framework are not
applicable to this type of analysis. One challenge is that the
security properties very much depend on the implementation
details. Fourth, it would be interesting to extend ADS to
accommodate more cryptographic applications.
via Assured Digital Signing
[attachment=65063]
Abstract—Digital signatures are an important mechanism for ensuring data trustworthiness via source authenticity, integrity, and
source nonrepudiation. However, their trustworthiness guarantee can be subverted in the real world by sophisticated attacks, which
can obtain cryptographically legitimate digital signatures without actually compromising the private signing key. This problem cannot be
adequately addressed by a purely cryptographic approach, by the revocation mechanism of Public Key Infrastructure (PKI) because it
may take a long time to detect the compromise, or by using tamper-resistant hardware because the attacker does not need to
compromise the hardware. This problem will become increasingly more important and evident because of stealthy malware (or
Advanced Persistent Threats). In this paper, we propose a novel solution, dubbed Assured Digital Signing (ADS), to enhancing the
data trustworthiness vouched by digital signatures. In order to minimize the modifications to the Trusted Computing Base (TCB), ADS
simultaneously takes advantage of trusted computing and virtualization technologies. Specifically, ADS allows a signature verifier to
examine not only a signature’s cryptographic validity but also its system security validity that the private signing key and the signing
function are secure, despite the powerful attack that the signing application program and the general-purpose Operating System (OS)
kernel are malicious. The modular design of ADS makes it application-transparent (i.e., no need to modify the application source code
in order to deploy it) and almost hypervisor-independent (i.e., it can be implemented with any Type I hypervisor). To demonstrate the
feasibility of ADS, we report the implementation and analysis of an Xen-based ADS system.
INTRODUCTION
DIGITAL signatures are an important tool for ensuring
data trustworthiness. The cryptographic assurance of
digital signatures is well understood [1], assuming the
private signing keys are not compromised (despite sidechannel
attacks [2]). An appreciated problem is to attain a
stronger signature trustworthiness than the cryptographic
assurance. However, existing solutions to this problem are
not sufficient. Specifically, the cryptographic approach—including
digital signatures of various flavors: threshold
signature [3], proactive signatures [4], forward-secure
signature [5], [6], key-insulated signature [7], and intrusion-
resilient signatures [8]—can mitigate, but cannot prevent,
the compromise of signature trustworthiness. PKI-like
key revocation mechanisms are not sufficient because the
compromise may not be detected until after a long time. It is
also not sufficient to put the private signing keys in tamperresistant
hardware devices [9]. This is because the attacker
can compromise the signing functions without compromising
the private signing keys and without compromising the
hardware devices; for example, the attacker uses stealthy
malware to penetrate into the Operating System (OS) kernel
and then asks the device to sign the attacker’s messages [10],
[11]. In order to enhance signature trustworthiness in the
real world, we need to address such powerful attacks.
Our contributions. We propose enhancing data trustworthiness
via Assured Digital Signing (ADS), which allows a
signature verifier to examine not only digital signatures’
cryptographic validity as in the current daily routine
practice, but also their system security validity that the
private signing keys and the signing functions are secure. In
particular, ADS deals with the powerful attacks that the
signing application program itself may be malicious (e.g., a
backdoor was embedded by its vendor or developer), and
that the underlying general-purpose OS kernel is malicious.
In order to minimize the modifications to the Trusted
Computing Base (TCB), we propose a modular design of
ADS, which simultaneously takes advantage of trusted
computing and virtualization technologies.
We show that ADS can enhance digital signatures’
trustworthiness against the powerful attacks, as long as
(essentially) the hypervisor is secure. Although this assumption
is accepted by some researchers, it is deemed as
somewhat strong by others. We believe that hypervisors
will become significantly more secure in the near future (cf.
[12], [13], [14], [15], [16]). The modular design of ADS makes
it application-transparent because there is no need to modify
the application source code in order to deploy it, and almost
hypervisor-independent because it can be implemented on
any Type I hypervisor. The modular security analysis, albeit
informal, shows that if certain component properties are
MODULAR DESIGN AND SECURITY OF ADS
Now, we present the modular design of ADS.We argue that
ADS attains the desired security properties based on that
certain abstract component properties can be satisfied.
2.1 Design Requirements
The design requirements of ADS are: First, it should enhance
the trustworthiness of digital signatures by allowing a
signature verifier to examine not only the digital signatures’
cryptographic validity but also their security validity that
the private signing key and the signing function are secure.
This naturally suggests using some form of attestation.
Second, it should minimize the changes (if inevitable) to the
TCB. Third, it should be applicable to most, if not all, system
software platforms (i.e., platform independence) and should
not force modification of the application source code in
order to deploy it (i.e., application transparency).
The threat model consists of two attacks:
The Secure Communication Channel
Component
We propose using Xen’s shared memory mechanism to attain
the secure communication channel between the signing
application and the signing server. The reason for choosing
this mechanism, rather than the memory copy mechanism, is
not only that we can simplify the control over the protected
content (i.e., one copy in the case of memory mapping
versus multiple copies in the case of memory copy), but also
that memory mapping is more efficient especially when the
messages to be signed are in large volume.
As illustrated in Fig. 5, four physical memory regions,M0-
M3, are used as shared memory. SinceM0-M3 are mapped to
the user-VM, we need to protect them by making the
following changes to the page table entries (PTE) corresponding
to M0-M3. Specifically,
The Attestation Component
In order to measure the integrity of the signing application in
the user-VM, we need to know what comprises the
executable without relying on the user-VM kernel. Recall
that we measure the hash of application the executable and
the libraries (including the shared ones) the application
program calls, which exploits that in x86’s 32-bit PAE mode,
all code-segment pages are marked as “NX ¼¼ 0” if and
only if they are executable. When the signing application
program uses the call gate to request for signing service, the
DAI ET AL.: ENHANCING DATA TRUSTWORTHINESS VIA ASSURED DIGITAL SIGNING 843
Fig. 5. Highlight of the “shared memory”-based implementation of
secure communication channel. There are four physical memory
regions, M0-M3, with each of size 256 KBytes (which can be set as a
system parameter when installing ADS). M0 and M1 are mapped to the
user-VM’s kernel space for the security monitor itself, M2 and M3 are
mapped to the user-VM’s user space for the signing application, andM1,
M2, and M3 are mapped to the trusted-VM’s user space for the signing
server.M0 stores the code of the security monitor,M1 stores information
for attestation, M2 stores the message, and M3 stores the signature.
1. There is no practical way, if feasible at all, for the hypervisor to ensure
the integrity of the kernel module because the kernel module can make
many system calls, which can be compromised by the kernel.
hypervisor will compute the hash value of the application
program’s executable pages, write the hash value inM1, and
notify the policy engine. The policy engine compares this
measurement against the hash value of the application
program stored in the trusted-VM, which may be provided
by the software vendor or simply computed by the user at a
clean system state. If they match, the policy engine extends
this measurement into TPM’s PCR 9 for later attestation
purpose; otherwise, it prompts the user that the application
program in the user-VM has been corrupted. After the user
allows the signing request and the signing server generates a
digital signature, the signing server measures the hash value
of the message and the signature, and extends the hash value
to TPM’s PCR 11. Then, TPM’s standard attestation is
extended to accommodate PCR 9 and PCR 11, which allows
the signature verifier to examine the signing application, the
message and the signature. Note that all the hash values are
computed using SHA-256.
For applications that require to sign multiple signatures,
we propose the following cache-like performance enhancement.
Specifically, we allow the signing application to
request multiple signatures while amortizing the cost of
measuring the signing application program’s memory pages.
This can be achieved by locking the application program’s
executable pages so as to prevent the Time-of-Computing-to-
Time-of-Use (TOCTOU ) attack that can tamper the binary
after the measurement. As a result, the hypervisor only needs
to compute the hash value of the application program once
for signing multiple messages.
It is worthwhile to point out that if needed (e.g., when
ADS is used as a component in larger system), the attestation
service can be further extended to incorporate, for example,
the system call table and the Interrupt Descriptor Table (IDT)
in the user-VM. These tables do not change unless the kernel
is re-compiled and are often modified by attacks, which
means that this would allow detecting some attacks. If the
signing application needs to modify the Page Table Entries, it
can invoke call_gate(3,0) to unlock the memory. When the
signing application needs to use the signing service the next
time, it can invoke call_gate(1,0) to lock and measure the
executable pages again.
Performance Evaluation
The performance of the Xen-based ADS is mainly influenced
by three major factors: the time spent on the inter-VM
communication, the time spent on the digital signing, and
the time spent on attestation. In order to see which part is
the most time consuming, We first measure the time spent
on the inter-VM communication, then the ADS response
time but without attestation, finally the ADS response time
with attestation.
All experiments are performed on an HP xw4550 workstation,
with a quad-core 2.3 GHz AMD Opteron processor
and 4 GBytes of RAM. The machine has a v1.2 Broadcom
TPM, revision level A2. The software environment for all
experiments is paravirtualized Xen 3.3.1 installed on Ubuntu
8.04 LTS with the 2.6.18.8-xen kernel. The user-VM runs the
same paravirtualized kernel that is provided with Xen 3.3
and we give the Domain U 512MRAM and one virtual CPU
core. For the signing server, we use Peter Gutmann’s
cryptlib library version 3.3.3. We use PKCS#7 CMS
signing with RSA + SHA hash. The RSA key size was the
cryptlib default (2,048 bits).
Fig. 8a plots the inter-VM communication time with
varying size of messages, including the cost for protecting
M2. Each data point is averaged based on the 100,000
messages of the same size. We observe that for messages
with size up to 500 KBytes, the time is linearly related to
the message size; for messages with size exceeding
500 KBytes, the time is still linearly related to the message
size but with a smaller factor. This phenomenon is likely
that the AMD Opteron processor has 4 512 KBytes
L2 Cache, and the CPU optimization will give priority to
large (greater than 512 KBytes) and consecutive memory
access, which would occur in our experiment.
Fig. 8b plots the response time of ADS but without
attestation, where each point in the graph is averaged over
500 runs. For comparison purpose, it also plots the signing
cost with local cryptography library. We observe that the
differential is steadily about 0.01 seconds, which accommodates
the 0-0.006 seconds depicted in Fig. 8a, the time spent
on computing the hash value of the signing application, the
time spent on mapping the shared memory regions, and the
time spent on unmapping the shared memory regions after
obtaining the signature.
Fig. 8c plots ADS’s response time with TPM-based
attestation, where each point in the graph is averaged over
500 runs. For comparison purpose, it also plots ADS’
response time without attestation. We observe that there is
a large performance difference (about 5 seconds) between
using attestation and not using attestation. This is caused by
the underlying attestation technique and specific to the TPM
hardware platform in our experimental system. Specifically,
the noticeable cost is due to the TPM quote operation for
attestation, which is essentially for computing a 2,048-bit
RSA signature on the relevant PCR values, which takes about
5 seconds on the TPM’s low-end/cheap processor.
In summary, the inter-VM communication mechanism is
indeed very efficient, which justifies our design choice of
using the shared memory mechanism for this purpose. The
phenomenon that ADS’ response time is reasonably flat with
respect to varying size of messages is caused by 1) the inter-
VM communication mechanism is very efficient and only
consumes a very small portion of the response time, and
2) the TPM-specific attestation service consumes most part of
ADS’ response time but is independent of the size of the
messages because the attestation is always on the fixed-size
PCR values. We believe that the computational cost of TPMbased
attestation is not as significant as the security gain
implied by not causing many modifications to the hypervisor
(which would offer better performance). Moreover, any
performance improvement in TPM’s attestation service will
directly benefit ADS.
CONCLUSION
Enhancing signature trustworthiness is of fundamental
importance. We have presented a novel solution to this
problem, while dealing with malicious signing application
and/or malicious general-purpose OS kernel. To demonstrate
its feasibility, we reported a Xen-based implementation
and discussed the implementation issues on other Type I
hypervisor platforms.
Future research directions. There are opportunities for
future research. First, it is important to reduce, if not
eliminate, the reliance on the user to confirm that a message
signing operation was indeed initiated by a human user.
Second, we observe that the user confirmation mechanism
offers enhanced source nonrepudiation, which could be
exploited to hold insiders (i.e., corrupt authorized users)
more accountable. This is because they cannot attribute
signatures to the attacks we addressed. As such, it is
interesting to characterize to what extent accountability can
be gained by deploying ADS. Third, it would be very
interesting to formalize the type of (modular) security
analysis we conducted. It appears that both the cryptographic
framework and the Dolev-Yao framework are not
applicable to this type of analysis. One challenge is that the
security properties very much depend on the implementation
details. Fourth, it would be interesting to extend ADS to
accommodate more cryptographic applications.