---
_id: '18'
abstract:
- lang: eng
  text: "Branch and bound (B&B) algorithms structure the search space as a tree and
    eliminate infeasible solutions early by pruning subtrees that cannot lead to a
    valid or optimal solution. Custom hardware designs significantly accelerate the
    execution of these algorithms. In this article, we demonstrate a high-performance
    B&B implementation on FPGAs. First, we identify general elements of B&B algorithms
    and describe their implementation as a finite state machine. Then, we introduce
    workers that autonomously cooperate using work stealing to allow parallel execution
    and full utilization of the target FPGA. Finally, we explore advantages of instance-specific
    designs that target a specific problem instance to improve performance.\r\n\r\nWe
    evaluate our concepts by applying them to a branch and bound problem, the reconstruction
    of corrupted AES keys obtained from cold-boot attacks. The evaluation shows that
    our work stealing approach is scalable with the available resources and provides
    speedups proportional to the number of workers. Instance-specific designs allow
    us to achieve an overall speedup of 47 × compared to the fastest implementation
    of AES key reconstruction so far. Finally, we demonstrate how instance-specific
    designs can be generated just-in-time such that the provided speedups outweigh
    the additional time required for design synthesis."
author:
- first_name: Heinrich
  full_name: Riebler, Heinrich
  id: '8961'
  last_name: Riebler
- first_name: Michael
  full_name: Lass, Michael
  id: '24135'
  last_name: Lass
  orcid: 0000-0002-5708-7632
- first_name: Robert
  full_name: Mittendorf, Robert
  last_name: Mittendorf
- first_name: Thomas
  full_name: Löcke, Thomas
  last_name: Löcke
- first_name: Christian
  full_name: Plessl, Christian
  id: '16153'
  last_name: Plessl
  orcid: 0000-0001-5728-9982
citation:
  ama: Riebler H, Lass M, Mittendorf R, Löcke T, Plessl C. Efficient Branch and Bound
    on FPGAs Using Work Stealing and Instance-Specific Designs. <i>ACM Transactions
    on Reconfigurable Technology and Systems (TRETS)</i>. 2017;10(3):24:1-24:23. doi:<a
    href="https://doi.org/10.1145/3053687">10.1145/3053687</a>
  apa: Riebler, H., Lass, M., Mittendorf, R., Löcke, T., &#38; Plessl, C. (2017).
    Efficient Branch and Bound on FPGAs Using Work Stealing and Instance-Specific
    Designs. <i>ACM Transactions on Reconfigurable Technology and Systems (TRETS)</i>,
    <i>10</i>(3), 24:1-24:23. <a href="https://doi.org/10.1145/3053687">https://doi.org/10.1145/3053687</a>
  bibtex: '@article{Riebler_Lass_Mittendorf_Löcke_Plessl_2017, title={Efficient Branch
    and Bound on FPGAs Using Work Stealing and Instance-Specific Designs}, volume={10},
    DOI={<a href="https://doi.org/10.1145/3053687">10.1145/3053687</a>}, number={3},
    journal={ACM Transactions on Reconfigurable Technology and Systems (TRETS)}, publisher={Association
    for Computing Machinery (ACM)}, author={Riebler, Heinrich and Lass, Michael and
    Mittendorf, Robert and Löcke, Thomas and Plessl, Christian}, year={2017}, pages={24:1-24:23}
    }'
  chicago: 'Riebler, Heinrich, Michael Lass, Robert Mittendorf, Thomas Löcke, and
    Christian Plessl. “Efficient Branch and Bound on FPGAs Using Work Stealing and
    Instance-Specific Designs.” <i>ACM Transactions on Reconfigurable Technology and
    Systems (TRETS)</i> 10, no. 3 (2017): 24:1-24:23. <a href="https://doi.org/10.1145/3053687">https://doi.org/10.1145/3053687</a>.'
  ieee: 'H. Riebler, M. Lass, R. Mittendorf, T. Löcke, and C. Plessl, “Efficient Branch
    and Bound on FPGAs Using Work Stealing and Instance-Specific Designs,” <i>ACM
    Transactions on Reconfigurable Technology and Systems (TRETS)</i>, vol. 10, no.
    3, p. 24:1-24:23, 2017, doi: <a href="https://doi.org/10.1145/3053687">10.1145/3053687</a>.'
  mla: Riebler, Heinrich, et al. “Efficient Branch and Bound on FPGAs Using Work Stealing
    and Instance-Specific Designs.” <i>ACM Transactions on Reconfigurable Technology
    and Systems (TRETS)</i>, vol. 10, no. 3, Association for Computing Machinery (ACM),
    2017, p. 24:1-24:23, doi:<a href="https://doi.org/10.1145/3053687">10.1145/3053687</a>.
  short: H. Riebler, M. Lass, R. Mittendorf, T. Löcke, C. Plessl, ACM Transactions
    on Reconfigurable Technology and Systems (TRETS) 10 (2017) 24:1-24:23.
date_created: 2017-07-25T14:17:32Z
date_updated: 2023-09-26T13:23:58Z
ddc:
- '000'
department:
- _id: '27'
- _id: '518'
doi: 10.1145/3053687
file:
- access_level: closed
  content_type: application/pdf
  creator: ups
  date_created: 2018-11-02T16:04:14Z
  date_updated: 2018-11-02T16:04:14Z
  file_id: '5322'
  file_name: a24-riebler.pdf
  file_size: 2131617
  relation: main_file
  success: 1
file_date_updated: 2018-11-02T16:04:14Z
has_accepted_license: '1'
intvolume: '        10'
issue: '3'
keyword:
- coldboot
language:
- iso: eng
page: 24:1-24:23
project:
- _id: '1'
  grant_number: '160364472'
  name: SFB 901
- _id: '4'
  name: SFB 901 - Project Area C
- _id: '14'
  grant_number: '160364472'
  name: SFB 901 - Subproject C2
- _id: '34'
  grant_number: '610996'
  name: Self-Adaptive Virtualisation-Aware High-Performance/Low-Energy Heterogeneous
    System Architectures
- _id: '52'
  name: Computing Resources Provided by the Paderborn Center for Parallel Computing
publication: ACM Transactions on Reconfigurable Technology and Systems (TRETS)
publication_identifier:
  issn:
  - 1936-7406
publication_status: published
publisher: Association for Computing Machinery (ACM)
quality_controlled: '1'
status: public
title: Efficient Branch and Bound on FPGAs Using Work Stealing and Instance-Specific
  Designs
type: journal_article
user_id: '15278'
volume: 10
year: '2017'
...
---
_id: '377'
abstract:
- lang: eng
  text: In this paper, we study how AES key schedules can be reconstructed from decayed
    memory. This operation is a crucial and time consuming operation when trying to
    break encryption systems with cold-boot attacks. In software, the reconstruction
    of the AES master key can be performed using a recursive, branch-and-bound tree-search
    algorithm that exploits redundancies in the key schedule for constraining the
    search space. In this work, we investigate how this branch-and-bound algorithm
    can be accelerated with FPGAs. We translated the recursive search procedure to
    a state machine with an explicit stack for each recursion level and create optimized
    datapaths to accelerate in particular the processing of the most frequently accessed
    tree levels. We support two different decay models, of which especially the more
    realistic non-idealized asymmetric decay model causes very high runtimes in software.
    Our implementation on a Maxeler dataflow computing system outperforms a software
    implementation for this model by up to 27x, which makes cold-boot attacks against
    AES practical even for high error rates.
author:
- first_name: Heinrich
  full_name: Riebler, Heinrich
  id: '8961'
  last_name: Riebler
- first_name: Tobias
  full_name: Kenter, Tobias
  id: '3145'
  last_name: Kenter
- first_name: Christian
  full_name: Plessl, Christian
  id: '16153'
  last_name: Plessl
  orcid: 0000-0001-5728-9982
- first_name: Christoph
  full_name: Sorge, Christoph
  last_name: Sorge
citation:
  ama: 'Riebler H, Kenter T, Plessl C, Sorge C. Reconstructing AES Key Schedules from
    Decayed Memory with FPGAs. In: <i>Proceedings of Field-Programmable Custom Computing
    Machines (FCCM)</i>. IEEE; 2014:222-229. doi:<a href="https://doi.org/10.1109/FCCM.2014.67">10.1109/FCCM.2014.67</a>'
  apa: Riebler, H., Kenter, T., Plessl, C., &#38; Sorge, C. (2014). Reconstructing
    AES Key Schedules from Decayed Memory with FPGAs. <i>Proceedings of Field-Programmable
    Custom Computing Machines (FCCM)</i>, 222–229. <a href="https://doi.org/10.1109/FCCM.2014.67">https://doi.org/10.1109/FCCM.2014.67</a>
  bibtex: '@inproceedings{Riebler_Kenter_Plessl_Sorge_2014, title={Reconstructing
    AES Key Schedules from Decayed Memory with FPGAs}, DOI={<a href="https://doi.org/10.1109/FCCM.2014.67">10.1109/FCCM.2014.67</a>},
    booktitle={Proceedings of Field-Programmable Custom Computing Machines (FCCM)},
    publisher={IEEE}, author={Riebler, Heinrich and Kenter, Tobias and Plessl, Christian
    and Sorge, Christoph}, year={2014}, pages={222–229} }'
  chicago: Riebler, Heinrich, Tobias Kenter, Christian Plessl, and Christoph Sorge.
    “Reconstructing AES Key Schedules from Decayed Memory with FPGAs.” In <i>Proceedings
    of Field-Programmable Custom Computing Machines (FCCM)</i>, 222–29. IEEE, 2014.
    <a href="https://doi.org/10.1109/FCCM.2014.67">https://doi.org/10.1109/FCCM.2014.67</a>.
  ieee: 'H. Riebler, T. Kenter, C. Plessl, and C. Sorge, “Reconstructing AES Key Schedules
    from Decayed Memory with FPGAs,” in <i>Proceedings of Field-Programmable Custom
    Computing Machines (FCCM)</i>, 2014, pp. 222–229, doi: <a href="https://doi.org/10.1109/FCCM.2014.67">10.1109/FCCM.2014.67</a>.'
  mla: Riebler, Heinrich, et al. “Reconstructing AES Key Schedules from Decayed Memory
    with FPGAs.” <i>Proceedings of Field-Programmable Custom Computing Machines (FCCM)</i>,
    IEEE, 2014, pp. 222–29, doi:<a href="https://doi.org/10.1109/FCCM.2014.67">10.1109/FCCM.2014.67</a>.
  short: 'H. Riebler, T. Kenter, C. Plessl, C. Sorge, in: Proceedings of Field-Programmable
    Custom Computing Machines (FCCM), IEEE, 2014, pp. 222–229.'
date_created: 2017-10-17T12:42:05Z
date_updated: 2023-09-26T13:33:50Z
ddc:
- '040'
department:
- _id: '27'
- _id: '518'
- _id: '78'
doi: 10.1109/FCCM.2014.67
file:
- access_level: closed
  content_type: application/pdf
  creator: florida
  date_created: 2018-03-20T07:14:20Z
  date_updated: 2018-03-20T07:14:20Z
  file_id: '1397'
  file_name: 377-FCCM14.pdf
  file_size: 1003907
  relation: main_file
  success: 1
file_date_updated: 2018-03-20T07:14:20Z
has_accepted_license: '1'
keyword:
- coldboot
language:
- iso: eng
page: 222-229
project:
- _id: '1'
  grant_number: '160364472'
  name: SFB 901
- _id: '14'
  grant_number: '160364472'
  name: SFB 901 - Subprojekt C2
- _id: '4'
  name: SFB 901 - Project Area C
- _id: '34'
  grant_number: '610996'
  name: Self-Adaptive Virtualisation-Aware High-Performance/Low-Energy Heterogeneous
    System Architectures
publication: Proceedings of Field-Programmable Custom Computing Machines (FCCM)
publisher: IEEE
quality_controlled: '1'
status: public
title: Reconstructing AES Key Schedules from Decayed Memory with FPGAs
type: conference
user_id: '15278'
year: '2014'
...
---
_id: '521'
author:
- first_name: Heinrich
  full_name: Riebler, Heinrich
  id: '8961'
  last_name: Riebler
citation:
  ama: Riebler H. <i>Identifikation und Wiederherstellung von kryptographischen Schlüsseln
    mit FPGAs</i>. Universität Paderborn; 2013.
  apa: Riebler, H. (2013). <i>Identifikation und Wiederherstellung von kryptographischen
    Schlüsseln mit FPGAs</i>. Universität Paderborn.
  bibtex: '@book{Riebler_2013, title={Identifikation und Wiederherstellung von kryptographischen
    Schlüsseln mit FPGAs}, publisher={Universität Paderborn}, author={Riebler, Heinrich},
    year={2013} }'
  chicago: Riebler, Heinrich. <i>Identifikation und Wiederherstellung von kryptographischen
    Schlüsseln mit FPGAs</i>. Universität Paderborn, 2013.
  ieee: H. Riebler, <i>Identifikation und Wiederherstellung von kryptographischen
    Schlüsseln mit FPGAs</i>. Universität Paderborn, 2013.
  mla: Riebler, Heinrich. <i>Identifikation und Wiederherstellung von kryptographischen
    Schlüsseln mit FPGAs</i>. Universität Paderborn, 2013.
  short: H. Riebler, Identifikation und Wiederherstellung von kryptographischen Schlüsseln
    mit FPGAs, Universität Paderborn, 2013.
date_created: 2017-10-17T12:42:34Z
date_updated: 2022-01-06T07:01:46Z
department:
- _id: '27'
- _id: '518'
keyword:
- coldboot
language:
- iso: ger
project:
- _id: '1'
  name: SFB 901
- _id: '13'
  name: SFB 901 - Subprojekt C1
- _id: '14'
  name: SFB 901 - Subprojekt C2
- _id: '4'
  name: SFB 901 - Project Area C
publisher: Universität Paderborn
status: public
title: Identifikation und Wiederherstellung von kryptographischen Schlüsseln mit FPGAs
type: mastersthesis
user_id: '477'
year: '2013'
...
---
_id: '528'
abstract:
- lang: eng
  text: Cold-boot attacks exploit the fact that DRAM contents are not immediately
    lost when a PC is powered off. Instead the contents decay rather slowly, in particular
    if the DRAM chips are cooled to low temperatures. This effect opens an attack
    vector on cryptographic applications that keep decrypted keys in DRAM. An attacker
    with access to the target computer can reboot it or remove the RAM modules and
    quickly copy the RAM contents to non-volatile memory. By exploiting the known
    cryptographic structure of the cipher and layout of the key data in memory, in
    our application an AES key schedule with redundancy, the resulting memory image
    can be searched for sections that could correspond to decayed cryptographic keys;
    then, the attacker can attempt to reconstruct the original key. However, the runtime
    of these algorithms grows rapidly with increasing memory image size, error rate
    and complexity of the bit error model, which limits the practicability of the
    approach.In this work, we study how the algorithm for key search can be accelerated
    with custom computing machines. We present an FPGA-based architecture on a Maxeler
    dataflow computing system that outperforms a software implementation up to 205x,
    which significantly improves the practicability of cold-attacks against AES.
author:
- first_name: Heinrich
  full_name: Riebler, Heinrich
  id: '8961'
  last_name: Riebler
- first_name: Tobias
  full_name: Kenter, Tobias
  id: '3145'
  last_name: Kenter
- first_name: Christoph
  full_name: Sorge, Christoph
  last_name: Sorge
- first_name: Christian
  full_name: Plessl, Christian
  id: '16153'
  last_name: Plessl
  orcid: 0000-0001-5728-9982
citation:
  ama: 'Riebler H, Kenter T, Sorge C, Plessl C. FPGA-accelerated Key Search for Cold-Boot
    Attacks against AES. In: <i>Proceedings of the International Conference on Field-Programmable
    Technology (FPT)</i>. IEEE; 2013:386-389. doi:<a href="https://doi.org/10.1109/FPT.2013.6718394">10.1109/FPT.2013.6718394</a>'
  apa: Riebler, H., Kenter, T., Sorge, C., &#38; Plessl, C. (2013). FPGA-accelerated
    Key Search for Cold-Boot Attacks against AES. <i>Proceedings of the International
    Conference on Field-Programmable Technology (FPT)</i>, 386–389. <a href="https://doi.org/10.1109/FPT.2013.6718394">https://doi.org/10.1109/FPT.2013.6718394</a>
  bibtex: '@inproceedings{Riebler_Kenter_Sorge_Plessl_2013, title={FPGA-accelerated
    Key Search for Cold-Boot Attacks against AES}, DOI={<a href="https://doi.org/10.1109/FPT.2013.6718394">10.1109/FPT.2013.6718394</a>},
    booktitle={Proceedings of the International Conference on Field-Programmable Technology
    (FPT)}, publisher={IEEE}, author={Riebler, Heinrich and Kenter, Tobias and Sorge,
    Christoph and Plessl, Christian}, year={2013}, pages={386–389} }'
  chicago: Riebler, Heinrich, Tobias Kenter, Christoph Sorge, and Christian Plessl.
    “FPGA-Accelerated Key Search for Cold-Boot Attacks against AES.” In <i>Proceedings
    of the International Conference on Field-Programmable Technology (FPT)</i>, 386–89.
    IEEE, 2013. <a href="https://doi.org/10.1109/FPT.2013.6718394">https://doi.org/10.1109/FPT.2013.6718394</a>.
  ieee: 'H. Riebler, T. Kenter, C. Sorge, and C. Plessl, “FPGA-accelerated Key Search
    for Cold-Boot Attacks against AES,” in <i>Proceedings of the International Conference
    on Field-Programmable Technology (FPT)</i>, 2013, pp. 386–389, doi: <a href="https://doi.org/10.1109/FPT.2013.6718394">10.1109/FPT.2013.6718394</a>.'
  mla: Riebler, Heinrich, et al. “FPGA-Accelerated Key Search for Cold-Boot Attacks
    against AES.” <i>Proceedings of the International Conference on Field-Programmable
    Technology (FPT)</i>, IEEE, 2013, pp. 386–89, doi:<a href="https://doi.org/10.1109/FPT.2013.6718394">10.1109/FPT.2013.6718394</a>.
  short: 'H. Riebler, T. Kenter, C. Sorge, C. Plessl, in: Proceedings of the International
    Conference on Field-Programmable Technology (FPT), IEEE, 2013, pp. 386–389.'
date_created: 2017-10-17T12:42:35Z
date_updated: 2023-09-26T13:37:35Z
ddc:
- '040'
department:
- _id: '27'
- _id: '518'
- _id: '78'
doi: 10.1109/FPT.2013.6718394
file:
- access_level: closed
  content_type: application/pdf
  creator: florida
  date_created: 2018-03-15T10:36:08Z
  date_updated: 2018-03-15T10:36:08Z
  file_id: '1294'
  file_name: 528-plessl13_fpt.pdf
  file_size: 822680
  relation: main_file
  success: 1
file_date_updated: 2018-03-15T10:36:08Z
has_accepted_license: '1'
keyword:
- coldboot
language:
- iso: eng
page: 386-389
project:
- _id: '1'
  grant_number: '160364472'
  name: SFB 901
- _id: '14'
  grant_number: '160364472'
  name: SFB 901 - Subprojekt C2
- _id: '13'
  name: SFB 901 - Subproject C1
- _id: '4'
  name: SFB 901 - Project Area C
- _id: '34'
  grant_number: '610996'
  name: Self-Adaptive Virtualisation-Aware High-Performance/Low-Energy Heterogeneous
    System Architectures
publication: Proceedings of the International Conference on Field-Programmable Technology
  (FPT)
publisher: IEEE
quality_controlled: '1'
status: public
title: FPGA-accelerated Key Search for Cold-Boot Attacks against AES
type: conference
user_id: '15278'
year: '2013'
...