Show HN: RISC-V असेंबली टेबलटॉप बोर्ड गेम में विरोधी को हैक करना

 (punkx.org)
3 पॉइंट द्वारा GN⁺ 2023-10-01 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • PROJEKT: OVERFLOW एक सीखने वाला गेम है, जो RISC-V असेंबली और buffer overflow को बोर्ड गेम के नियमों में बदलता है, ताकि आप memory, stack और return address manipulation को सीधे फॉलो कर सकें
  • खिलाड़ी एक ही memory और program साझा करते हैं और virtual memory के बिना, हर turn में सिर्फ 10 instructions चलाने वाली preemptive scheduling शैली में मुकाबला करते हैं
  • खेल का फैसला मौजूदा instructions को कॉपी करके shellcode बनाने और विरोधी के return address को overwrite करके उसे game_over() पर भेजने की प्रक्रिया में होता है
  • गलत memory access, unaligned read/write और illegal instructions crash व exception handler execution तक ले जाते हैं; trap address बदलना और nop monkeypatch strategy के मुख्य variables हैं
  • Web play, printable board, ESP32 और mobile game helper दिए गए हैं, लेकिन कुछ rules अभी भी tweak हो रहे हैं, इसलिए यह experimental hacking puzzle के ज्यादा करीब है

गेम का लक्ष्य और execution model

  • PROJEKT: OVERFLOW एक project है जो RISC-V असेंबली और buffer overflow को tabletop board game के रूप में扱ता है
  • मुख्य लक्ष्य मौजूदा instructions को कॉपी करके memory में छोटा shellcode बनाना, buffer overflow से उस code पर jump करना, फिर विरोधी के return address को overwrite करके उससे game_over() function call करवाना है
  • Strategy सिर्फ code execution तक सीमित नहीं है; इसमें exception handler configuration और monkeypatch भी शामिल हैं
  • सभी खिलाड़ी वही memory और वही program साझा करते हैं, और time-sharing तरीके से वही processor इस्तेमाल करते हैं
    • एक turn में 10 instructions execute किए जाते हैं
    • हर खिलाड़ी का stack pointer अलग-अलग location से शुरू होता है
    • Virtual memory नहीं है

Build और board generation flow

  • Code को riscv64-unknown-elf-gcc से RV32 target के लिए compile किया जाता है
    • मुख्य options में -march=rv32g, -mabi=ilp32, -ffreestanding, -nostdlib, -nostartfiles, -O0 आदि शामिल हैं
    • -O0 की वजह से machine code verbose होता है, लेकिन follow करना आसान रहता है
  • Board के लिए material riscv64-unknown-elf-objdump -S -l -fd game output को parse करके बनाया जाता है
    • ▲ और ✎ instructions को modify किया जाता है
    • Jump offsets को hexadecimal से decimal में बदला जाता है
    • Assembly को साफ करके source code से match किया जाता है
    • SVG बनाया जाता है और फिर Inkscape से PDF में convert किया जाता है

Printing और तैयारी का सामान

  • Board को left और right में बंटे PDF print करके इस्तेमाल किया जाता है
  • Printing के लिए A3 बेहतर है; A4 भी संभव है, लेकिन छोटा पड़ेगा
  • जरूरी सामान: nop instruction के लिए 1 token, trap address के लिए 1 token, हर player के लिए program counter और stack pointer के 2 tokens, pencil और eraser
  • Web version single-player और friends के साथ play support करता है, और ESP32/mobile के लिए game helper भी उपलब्ध है

Basic rules और turn flow

  • शुरुआती state इस तरह है
    • सभी registers 0 से शुरू होते हैं, लेकिन return address register ra 1000 से शुरू होता है
    • Player 1 का sp 2244 और Player 2 का sp 3844 पर initialize होता है
    • दोनों players का pc main function के start address 1000 से शुरू होता है
    • Trap token address 1000 पर रखा जाता है
    • Preloaded program को छोड़कर सभी memory addresses 0 हैं
    • nop instruction token शुरुआत में board पर नहीं रखा जाता
  • एक turn में 10 instructions execute करने होते हैं, और jal, beq जैसे jumps को भी वैसे ही follow करना होता है
  • खिलाड़ी कम से कम 1 instruction execute करने के बाद turn रोककर बचे हुए instruction count को अगले turn में carry forward कर सकता है
    • जमा किए जा सकने वाले instruction count की maximum limit 20 है

Monkeypatch और जीत की शर्तें

  • हर turn की शुरुआत में ठीक 1 instruction execute करने के बाद, nop instruction token को किसी ऐसे function के arbitrary address पर ले जाया जा सकता है जिसे current players execute नहीं कर रहे हैं
  • जब pc उस address पर पहुंचता है, वह instruction no-operation की तरह काम करता है
  • nop token हिलाने पर current turn और next turn खो जाते हैं, और opponent अगले turn में maximum 20 instructions execute कर सकता है
  • Monkeypatch rule अभी balanced नहीं है, इसलिए हर कुछ दिनों में थोड़ा बदल रहा है
  • Hard mode में opponent को hack करके उससे game_over() function call करवाते ही game खत्म हो जाता है
  • अगर कोई भी side opponent को game_over() पर नहीं भेज सकती, तो draw है
  • Easy mode में main में ret execute करके main loop से बाहर निकलने वाला पहला player जीतता है

Special symbols और exception handling

  • ✎ li instruction के immediate value के रूप में 0 से 4095 तक का कोई भी 12-bit number चुनने देता है
  • ▲ load instruction में अपने stack pointer के आधार पर ±128 bytes range की value चुनने देता है
    • उदाहरण के लिए, अगर sp 2180 है, तो 2052 से 2308 तक चुना जा सकता है
  • Prohibited actions program crash की ओर ले जाते हैं
    • 1192 से कम memory address overwrite करना
    • 4 के multiple न होने वाले address पर unaligned read या write
    • Illegal instruction execute करना
  • Crash होने पर exception handler execute होता है और trap address पर jump करता है
    • Trap address शुरुआत में 1000 है, लेकिन set_trap() function में overwrite किया जा सकता है
    • Exception आने पर program counter को किसी specific value पर set किया जाता है और execution जारी रहता है
  • Cheating या गलती पकड़े जाने पर उस player की program state, memory और registers reset किए जाते हैं

3–4 खिलाड़ियों के expansion rules

  • Player 3 का sp 2116 पर set होता है
  • Player 4 का sp 3716 पर set होता है
  • 3 या उससे ज्यादा players होने पर ▲ symbol केवल stack pointer से -128 bytes दूर range में इस्तेमाल किया जा सकता है
  • 2 से ज्यादा players के साथ खेल काफी unstable हो जाता है और जल्दी corrupt हो जाता है
  • जीत की शर्त तक पहुंचना और मुश्किल हो जाता है, लेकिन gameplay ज्यादा मजेदार और chaotic हो जाता है

Hacking strategy examples

  • Crash को opponent की progress रोकने वाली attack strategy के रूप में इस्तेमाल किया जा सकता है
  • अगर trap handler को game_over function में बदल दिया जाए, तो जो player सबसे पहले crash करेगा वह हार जाएगा
    • इस state में nop token बहुत powerful हो जाता है
    • अगर opponent अभी जिस function को execute कर रहा है, उसके ret पर nop रख दिया जाए, तो opponent हार सकता है
  • bug() function में index को 400 या -400 से overflow करने पर opponent के stack तक पहुंचकर return address overwrite किया जा सकता है
    • उदाहरण के लिए address 3784 से 2184 पर जाने के लिए (3784 - 2184) / 4 = 400 है, इसलिए index -400 चाहिए
  • copy() function से specific instructions को कॉपी करके memory में छोटा shellcode बनाया जा सकता है
    • Example shellcode li a4, ✎, li a5, ✎, sw a4, 0(a5), ret combination से arbitrary write करता है
    • ret instruction कॉपी करने पर return address shellcode start point पर set हो जाता है और infinite loop बन जाता है
  • bug() function में index को 6 set करने पर value variable को stack में saved return address यानी 28(sp) के ऊपर लिखा जा सकता है
    • bug() से return करते समय 28(sp) की value return address register में कॉपी होती है
    • अगर इस value में बनाए गए shellcode का address डाल दें, तो memory में jump किया जा सकता है

Instruction interpretation और changes

  • सभी jumps current program counter के relative jumps हैं, भले ही disassembler में वे absolute addresses जैसे दिखें
    • उदाहरण के लिए jal a4, 0 का machine code 1903 execution के समय infinite loop बन जाता है
  • Valid game instructions की list machine code 0 से 4095 तक के RV32 JRI instructions में से a0, a4, a5, sp, ra आदि का उपयोग करने वाले forms के रूप में व्यवस्थित है
  • Changelog 0.0.6 में while(run) की जगह while(*prun) इस्तेमाल करने वाला change शामिल है
    • Opponent unaligned dereference induce करके force crash करा सकता है
    • NOP rule बदलकर केवल उन functions पर placement allow करता है जो currently execute नहीं हो रहे

Design और learning resources

  • Board के left/right sides के squares ASCII-encoded binary message हैं
    • White squares 1 हैं, black squares 0 हैं
  • Colors cheap printing और black-and-white printer readability के लिए सिर्फ red, blue, black और white रखे गए हैं
  • Syntax highlighting इस्तेमाल नहीं की गई है
    • Theme के आधार पर code के कुछ हिस्सों को ज्यादा important दिखाने के effect से बचने और खुद judge करते हुए focus करने के लिए यह choice है
  • RISC-V assembly learning resources में riscv-programming.org, cs3410 risc-v interpreter, luplab का rvcodecjs आदि हैं
  • C learning resource के रूप में Beej's Guide to C Programming के शुरुआती हिस्से इस्तेमाल किए गए हैं
  • Variables, function calls, pointers, strings, structs, arrays, recursion आदि cover करने वाले printable assembly practice PDF और fill-in-the-blanks style “assembly hangman” version उपलब्ध हैं

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2023-10-01
Hacker News की रायें

  • वाकई प्रभावशाली। खासकर यह बात सबसे कमाल की लगती है कि उन्होंने अपनी 12 साल की बेटी को भी इसमें साथ खेलने के लिए तैयार कर लिया
    CHERI वर्ज़न कब तक उम्मीद करें? :-D

    • “CHERI के तीन मुख्य design goals हैं: fine-grained memory protection और scalable software isolation के लिए processor support के ज़रिए आधुनिक C भाषा TCB की सुरक्षा को काफी बेहतर करना; और कभी-कभी आपस में टकराने वाली requirements के कारण design में सावधानी से संतुलन बनाना पड़ा” — इस तरह की बात है, इसलिए CHERI वर्ज़न मुश्किल लगता है :)
    • मैंने 12 साल की उम्र में 6502 assembly लिखी थी। आज के computer environment में 12 साल के बच्चे के लिए ऐसा करना आसान नहीं है
    • 8-bit दौर में computer शुरू करने की यह आम उम्र थी

  • Core War एक game है जो एक virtual machine के memory arena में खेला जाता है, जिसमें सरल simulated assembly language support होती है। मैंने इसे पहली बार 1984 में Scientific American में देखा था, और तब तक मैं करीब 15 साल से programming कर रहा था, इसलिए समझ गया था कि यह Bell Labs के पुराने game Darwin से प्रेरित था
    Darwin 1961 में बना था और IBM 7090 पर चलता था। Programs resources के लिए मुकाबला करते थे, और जो program allocated space की पूरी नकल करके कब्ज़ा कर लेता था, वह जीतता था। Robert Morris Sr. ने एक अजेय program बना दिया, जिसके बाद यह ज्यादा समय तक नहीं चला। [2] देखें
    1970s के मध्य में Software Practice and Experience मेरे पसंदीदा computer science journals में से एक था, और उसमें Aleph-Null नाम के pen name से लिखे Computer Recreations columns अक्सर छपते थे। Graduate school के दिनों में मैंने उस column में आए कई games implement करके खूब मज़ा लिया। Journal महंगा है, लेकिन अगर आप college student हैं तो शायद मेरी तरह university library में पुराने अंक मिल जाएं। 1970s के issues में Pascal compiler, Algol 68, concurrent programming जैसे topics थे—पढ़ने में आसान और मज़ेदार—और N. Wirth के लेखों से मुझे Module[3,4] और बाद में Oberon[5] के बारे में पता चला
    [1] https://en.wikipedia.org/wiki/Core_War
    [2] https://en.wikipedia.org/wiki/Darwin_(programming_game)
    [3] https://onlinelibrary.wiley.com/doi/abs/10.1002/spe.43800701...
    [4] https://onlinelibrary.wiley.com/doi/abs/10.1002/spe.43800701...
    [5] https://onlinelibrary.wiley.com/doi/abs/10.1002/spe.43801909...

  • मेरा एक दोस्त था जो कहता था कि उसे games पसंद हैं लेकिन coding वाला दिमाग नहीं है। Human Resource Machine के ज़रिए वह असल में coding करने लगा, और उसकी कुछ solutions मेरे कई सालों के experience वाली solutions से भी बेहतर थीं

    • कभी-कभी नया perspective उम्मीद से कहीं ज्यादा मदद करता है
      मेरा 12 साल का बच्चा math से नफरत करता है, लेकिन Human Resource Machine और SpaceChem में हैरान करने लायक अच्छा है। सोचता हूं कि high school math और programming की math क्या fundamentally अलग हैं

  • बहुत दिलचस्प। आजकल computer memory के size को देखते हुए मुझे हमेशा लगता रहा है कि छोटे mnemonics engineering के लिहाज़ से अच्छा चुनाव नहीं हैं
    यहां भी सबसे पहला काम यह सीखना और याद रखना है कि instruction क्या करता है। अगर names को ज्यादा descriptive रूप में बदल दिया जाए तो सीखना, याद रखना और code पढ़ना बहुत आसान हो जाएगा। लोग अक्सर ऐसा नहीं करते, यह बात मुझे संदिग्ध लगती है
    यह तथ्य कि इस तरह की vulnerability संभव है, मेरे हिसाब से पूरे system design की failure दिखाता है। इसका मतलब यह नहीं कि यह मज़ेदार game नहीं है या सीखने का अच्छा तरीका नहीं है, लेकिन engineering में structural problems बहुत आसानी से स्वीकार कर लिए जाते हैं। ज्यादातर लोग उस structural flaw को देख भी नहीं पाते

    • पहले version में कहीं ज्यादा readable pseudo-assembly थी, और मैंने उस दिशा पर भी सोचा था। लेकिन आखिर में मैं चाहता था कि मेरी बेटी objdump output आराम से पढ़ सके, और कुछ mnemonics सीखना मुझे कोई बड़ी समस्या नहीं लगता
      मुझे लगता है बच्चे तब बहुत अच्छा respond करते हैं जब उन्हें कमतर नहीं आंका जाता। कम से कम मेरे बच्चे के साथ तो ऐसा ही था
      क्या आपको लगता है कि कोई ऐसा है जो arbitrary read और write को structural flaw नहीं मानता? हजारों लोग उस समस्या पर काम कर रहे हैं और काफी progress भी कर रहे हैं। साथ ही, मुझे अब भी लगता है कि peek और poke मज़ेदार हैं

  • यह सच में शानदार है। ऑफिस में इसे try करना चाहूंगा

  • काफी मज़ेदार लग रहा है। आपके हिसाब से यह किस age group के लिए सही है?

    • आसान जीत की condition, यानी bug() में quick buffer overflow करके main loop से बाहर निकलना, मुझे लगता है 10–15 साल के बच्चे भी कर सकते हैं
      मेरी बेटी 12 साल की है और हम साथ में मज़े से खेल रहे हैं। कठिन जीत की condition, यानी opponent को game_over() function पर jump करवाना, ज्यादा मुश्किल है, लेकिन लगता है 5–6 महीनों में वहां तक पहुंच सकते हैं
      Adults के बारे में पक्का नहीं कह सकता। कुछ लोग assembly से ऐसे डरते हैं जैसे उसे शैतान ने बनाया हो, इसलिए उन्हें बच्चों से भी ज्यादा मुश्किल से खेलने के लिए मनाया जा सकता है

  • दिलचस्प बात यह है कि हम दुनिया को अपने ही आईने की तरह देखने की प्रवृत्ति रखते हैं
    मैं buffer overflow और programming में interested हूं, तो मेरी बेटी भी ज़रूर बहुत interested होगी—यह मानना कितना संभावित है? अगर वह पहला बच्चा हो और दूसरी बात, लड़की हो, तो probability और भी कम लगती है, फिर भी मैंने कई पिताओं को आगे बढ़ते देखा है
    ऐसे project करते समय क्या कम से कम कुछ हद तक यह vanity project है, इसका एहसास था—यह जानने की उत्सुकता है। खैर, मुझे ऐसी चीज़ों में रुचि है, इसलिए इसे public करने के लिए खुशी है

    • यह और भी दिलचस्प है कि लोग अपनी बात को plausible बनाने के लिए कितनी बड़ी-बड़ी assumptions बेझिझक कर लेते हैं
      आप संकेत दे रहे हैं कि project creator अपनी vanity के कारण बेटी पर यह चीज़ थोप रहा है—इसका आधार क्या है? मैंने site के कुछ pages देखे, लेकिन ऐसा संकेत देने वाली कोई बात नहीं मिली; उल्टा कई जगह नरम भाषा में लिखा था कि बेटी इसे enjoy कर रही है और काफी interested है
      आप यह संभावना क्यों exclude कर रहे हैं कि बेटी ने ही पहले curiosity दिखाई हो कि पापा computer पर क्या करते हैं? बात छोटी शुरू हुई हो और फिर interest share करने वाले इंसान और एक छोटे co-explorer के बीच दो-तरफा process बन गई हो
      असल में क्या है, मुझे भी नहीं पता, लेकिन आपको भी नहीं पता। Education में कुछ साल involved रहने के अनुभव से कह सकता हूं कि बच्चे आम तौर पर जितना माना जाता है, उससे कहीं बेहतर learners होते हैं। School structure भी एक वजह हो सकती है, लेकिन core में ऐसी limiting beliefs भी हो सकती हैं। इस पिता को सलाम, जिसने अपनी बेटी और दुनिया के साथ अपनी रुचि और passion share करने की कोशिश की
    • एक पिता के तौर पर मैं बस वह सब सिखाने की कोशिश कर रहा हूं जो मैं सिखा सकता हूं। कभी programming होती है, कभी fighting, कभी meditation
      उनमें से कुछ चीज़ें valuable होंगी और कुछ नहीं। Odds हमेशा खिलाफ होते हैं। ज़िंदगी ऐसी ही है

  • जब 64-bit RISC-V code path stable हो जाएगा, काफी अच्छे से काम करेगा और “buffer overflow” भी गायब हो जाएगा, तब C/C++ हमेशा syntax बदलकर साथ नहीं देगा—ऐसी स्थिति में planned obsolescence का क्या करोगे? बेचारे लोग…

  • एक मिनट।
    tabletop board game जिसमें assembly coding शामिल है? मैंने यह पहले क्यों नहीं सोचा? :D

  • PL/I ने string/array bounds checking, नीचे की बजाय ऊपर की ओर बढ़ने वाले stack जैसी चीज़ें सही की थीं
    https://www.acsac.org/2002/papers/classic-multics.pdf