जब यह सचमुच random नहीं होता

 (orlp.net)
2 पॉइंट द्वारा GN⁺ 2024-01-15 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • World of Warcraft का Lua addon environment UI को आसानी से बदलने देता था, लेकिन game actions की automation रोकने के लिए information access और execution permissions को अलग रखा गया था
  • Blizzard के security model ने बहुत-सी जानकारी पढ़ने वाले non-secure environment और actions करने वाले secure environment को अलग किया, और यही सीमा automation रोकने की कुंजी थी
  • secure environment में allowed random, MSVC C rand का एक पतला wrapper था, और shared global state वाला कमजोर linear congruential generator होने के कारण यह information-passing channel बन सकता था
  • RNG के सिर्फ दो outputs से internal state candidates को अधिकतम 8 तक घटाया जा सकता था, और अतिरिक्त output से एक candidate चुनने के बाद desired action index आने तक RNG को आगे बढ़ाया जा सकता था
  • ऊपर से यह random action selection जैसा दिखता था, लेकिन वास्तव में desired spell जैसे action को चुनवाया जा सकता था; बाद में Blizzard ने इसे किस तरह fix किया, यह स्पष्ट नहीं है

World of Warcraft addons programming की शुरुआत बने

  • World of Warcraft addons की बनावट ऐसी थी कि Lua में लिखी कुछ .lua source files को एक folder में रखने पर game उन्हें सीधे load कर लेता था
  • files को edit और save करके interface reload करने पर result तुरंत दिख जाता था, इसलिए entry barrier बहुत कम था
  • शुरुआत में दूसरों का code copy करके, refactor करके या recombine करके मनचाहे features बनाने के तरीके से कई addons बनाए गए
  • समय के साथ actual gameplay से ज्यादा समय addon लिखने में जाने लगा, और World of Warcraft गंभीरता से programming शुरू करने की वजह बना

Blizzard का addon security model

  • अगर users पूरी तरह programmable addons बना सकें तो bots की समस्या हो सकती थी, इसलिए Blizzard ने एक ऐसी structure बनाई जो आम players द्वारा संभव automation को सीमित करती थी
  • अधिकांश UI elements और information-gathering APIs बिना रोक-टोक इस्तेमाल किए जा सकते थे
    • उदाहरण के लिए character health पढ़कर foreground frame का size adjust करने वाला health bar बनाया जा सकता था
  • character movement, spell casting, item use जैसे actual game actions करने वाली APIs protected थीं और सिर्फ official Blizzard code से call की जा सकती थीं
  • exact world position और camera direction पाने वाली APIs भी किसी समय से protected हो गईं
    • यह boss fights को आसान बनाने के लिए game world के ऊपर 3D elements draw करने वाले addons के जवाब में किया गया कदम था

secure और non-secure environments का separation

  • कुछ UI elements को actual game actions से interact करना होता था, इसलिए click पर secure environment में code चलाने वाले special buttons बनाए जा सकते थे
  • ऐसे buttons combat के दौरान create, delete या move नहीं किए जा सकते थे
    • इससे combat के दौरान cursor के नीचे conditionally button रखकर actions automate करने का तरीका blocked हो गया
  • secure environment programmatically यह set कर सकता था कि कौन-सा spell cast करना है, लेकिन arbitrary automation के लिए जरूरी external state access रोक दिया गया था
  • macro system level की कुछ information-gathering APIs ही allowed थीं, और optimal spell selection के लिए जरूरी जानकारी, जैसे ability cooldown या unit health, उपलब्ध नहीं थी
  • नतीजतन दोनों environments के permissions अलग थे
    • non-secure environment: बहुत जानकारी पा सकता है, लेकिन action नहीं कर सकता
    • secure environment: action कर सकता है, लेकिन automation के लिए जरूरी जानकारी नहीं पा सकता

random एक backdoor channel बन गया

  • लक्ष्य third-party software से security restrictions बंद करना नहीं था, बल्कि यह देखना था कि सिर्फ technically allowed tools से secure environment को bypass किया जा सकता है या नहीं
  • secure environment में allowed functions की list देखते समय random मिला
  • computer के random number generators अधिकतर internal state वाले pseudorandom number generators होते हैं, इसलिए लगा कि अगर उस state को manipulate किया जा सके तो external information secure environment तक पहुंचाई जा सकती है
  • असल random, C के rand के ऊपर एक छोटा wrapper था
  • क्योंकि World of Warcraft MSVC से compile हुआ था, rand implementation global state-based generator था
uint32_t state;

int rand() {
    state = state * 214013 + 2531011;
    return (state >> 16) & 0x7fff;
}
  • यह implementation process में single global random state share करता था और एक कमजोर linear congruential generator था

MSVC rand state recovery

  • rand output state के एक हिस्से, यानी 15 bits, को सीधे expose करता है
  • state space छोटा है और output का कुछ हिस्सा दिखता है, इसलिए possible state candidates बनाए रखते हुए additional outputs से candidates हटाए जा सकते हैं
  • ज्यादा efficient तरीका यह है कि RNG के दो outputs r0, r1 observe करके hidden 16-bit state part के candidates calculate किए जाएं
  • MSVC rand के constants ये हैं
    • a = 214013
    • b = 2531011
  • पहली और दूसरी call के बाद के hidden 16-bit हिस्सों को क्रमशः h0, h1 मानें, तो state transition equation से h0 candidates derive किए जा सकते हैं
  • calculation में k के लिए सिर्फ -1 <= k < 7 range देखनी पड़ती है, इसलिए hidden state candidates अधिकतम 8 तक घट जाते हैं
  • इसके बाद additional RNG call result की तुलना candidate RNG के output से करके गलत candidates हटाए जाते हैं
  • example Python implementation में while loop इस्तेमाल हुआ था, लेकिन practice में third output तक single candidate तक narrow down हो जाता दिखा
  • उस समय यह discrete-math derivation खुद करना मुश्किल था, इसलिए crypto.SE पर सवाल पूछा और वजह दी कि “मैं colleague को दिखाना चाहता हूं कि यह RNG कितना कमजोर है”

secure environment में desired action चुनने का तरीका

  • RNG internal state recover कर पाने के बाद secure environment तक arbitrary automation decisions भेजे जा सकते थे
  • process इस तरह था
    • secure environment code चलने से ठीक पहले execute होने वाला non-secure hook register किया जाता
    • hook के अंदर सभी information access की जा सकती थी, इसलिए तय किया जाता कि कौन-सा action करना है
    • चुने गए action को hardcoded action list में ढूंढकर index में बदला जाता
    • ऊपर वाले तरीके से current RNG state recover की जाती
    • अगर अगला RNG output, action list length से divide करने पर remainder के हिसाब से desired index नहीं होता, तो RNG को advance करके फिर check किया जाता
    • जब desired output आने की बारी होती, hook return करता, और secure environment random call करके उस index का action perform करता
  • secure environment में यह random number से action list index करने जैसा दिखता है, लेकिन असल में अगले random call का timing control करके desired action चुना जाता है
  • अगर action list size n हो, तो desired value भेजने के लिए औसतन RNG को n steps advance करना पड़ता था, लेकिन actual use में यह समस्या नहीं थी

बाद की स्थिति

  • कुछ साल बाद दोबारा कोशिश करने पर यह तरीका अब काम नहीं कर रहा था
  • Blizzard ने कमजोर और shared RNG state की समस्या कब fix की, या इसे समस्या माना भी या नहीं, यह पता नहीं है
  • संभावित changes में दूसरे algorithm पर switch करना या secure environment के लिए सही तरह से separated RNG state रखना शामिल है
  • यह इस्तेमाल करने के लिए लिखा गया code नहीं था, लेकिन दिखने में random चीज को desired result में manipulate करने में सफल एक सीमित scope वाला game security bypass case था

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

1 टिप्पणियां

 
GN⁺ 2024-01-15
Hacker News टिप्पणियाँ

  • बहुत पहले, जब मैं WoW GM के रूप में काम करता था, लोकप्रिय ऐड-ऑन Titan Bar के एक खास वर्ज़न में बग था, जिसकी वजह से वह “GM को टिकट लिखें” UI दिखाने वाली API को बार-बार कॉल करता रहता था
    कैंसल करने पर भी वह फिर से खुल जाता था, और समस्या पैदा करने वाले ऐड-ऑन को हटाने के अलावा, उस विंडो से छुटकारा पाने का बस यही तरीका था कि टेक्स्ट बॉक्स में कुछ लिखकर सबमिट किया जाए
    GM के नज़रिए से वे एक-दो दिन सचमुच बहुत कठिन थे, और कई प्लेयर्स को यह भी पता नहीं था कि GM क्या होता है, या वे टिकट भेज सकते हैं
    “ग्राहक जी, शायद आपने किसी ऐड-ऑन की वजह से टिकट सबमिट किया है, इसलिए ग्राहक सहायता प्रतिनिधि के रूप में मैं आपसे संपर्क कर रहा हूँ” यह समझाना भी आम तौर पर आसान नहीं था
    इसने सामान्य response time को व्यावहारिक रूप से बिगाड़ दिया था, इसलिए डेवलपर्स ने hotfix निकाला और उस API call को Blizzard के अपने LUA code से ही संभव बनाने के लिए protection के पीछे डाल दिया

    • नाम शायद Titan Panel था
      यह ऐसा ऐड-ऑन था जो कुल gold, repair percentage जैसे कई UI elements को एक लाइन वाले bar में जोड़ देता था

  • अजीब बात है कि लगभग इसी “random number generator को reverse solve करने” वाले सवाल पर, Crypto.SE पर सवाल आने से कुछ महीने पहले मैंने StackOverflow पर जवाब दिया था: https://stackoverflow.com/a/15237585/1204143
    हालांकि MSVC random generator की जगह मैंने Java random generator पर हमला किया था
    दोनों ही internal state के काटे हुए values output करने वाले सरल linear congruential generator (LCG) ढांचे हैं, इसलिए attack method भी दोनों में बहुत मिलती-जुलती है

    • मैं maths में बहुत अच्छा नहीं हूँ, इसलिए Z3 से कहा कि वह कोई सुविधाजनक seed ढूँढ दे, और उसका नतीजा नीचे वाला code था
      import java.util.Random;
      public class Hayley {
      public static void main(String... args) {
      byte[] b1 = new byte[4], b2 = new byte[2];
      (new Random(0x2effe2140e00L)).nextBytes(b1);
      (new Random(0xc2f0097)).nextBytes(b2);
      System.out.println(new String(b1) + new String(b2));
      }
      }

  • जिज्ञासा है कि क्या server पर भी वही random number generator इस्तेमाल हुआ होगा
    अगर ऐसा था, तो बहुत कम usage वाले server, कम latency, मौजूदा random generator state को काफी सटीकता से सीमित कर पाने की क्षमता, और random पर निर्भर बड़े आर्थिक अंतर वाले event को जल्दी-जल्दी दोबारा trigger कर पाने की क्षमता होने पर, सिद्धांततः इसका दुरुपयोग संभव लगता है

    • Vanilla WoW servers ने Mersenne Twister इस्तेमाल किया था, और उसमें कई तरह की समस्याएँ तो थीं, लेकिन वह इतनी मामूली तरह से नहीं टूटता था
      Blizzard ने अंधविश्वासी players में फैली “loot seed” जैसी चीज़ों वाली अफवाहें खत्म करने की, कुल मिलाकर असफल कोशिश में, server-side random generation method की काफी details सार्वजनिक की थीं

  • random number generators की economics और incentives दिलचस्प हैं
    अगर वास्तव में कुछ दाँव पर नहीं है और लोग आसानी से पहचान नहीं सकते, तो game जैसे use case में अधूरे या यहाँ तक कि खराब random number generators भी काफी हो सकते हैं
    लेकिन cryptocurrency wallets या online casinos जैसी जगहों पर, जहाँ पैसा या security दाँव पर हो, यह अचानक बेहद महत्वपूर्ण हो जाता है

  • और गंभीर बात यह है कि दिया गया linear congruential random number generator केवल 12,445 अलग-अलग numbers बनाने के बाद repeat हो जाता है
    इसी algorithm में बेहतर parameters इस्तेमाल करना भी कहीं अधिक वाजिब होता

    • engineering समझौते का नाम है
      smoke trails में particles की movement जैसे सरल कामों के लिए सरल लेकिन तेज़ random number generator चाहिए होता है
      cryptography या casino games वगैरह में न सिर्फ कम-से-कम 32-byte state वाला बेहतर random number generator इस्तेमाल किया जाता है, बल्कि results का अनुमान लगाना और कठिन बनाने के लिए engine को random intervals पर extra advance भी किया जाता है

  • World of Warcraft ही वह वजह था जिससे programming में मेरी रुचि पैदा हुई
    launch के समय मैं 6 साल का था, और जब private servers आने लगे, तो मुझे खुद NPC बनाना सीखने की जिज्ञासा हुई और मैंने Lua सीखी
    उस समय जिन MMOwned forums पर मैं सक्रिय था, उनके काफी posts आज भी बचे हैं, और जिन लोगों में से एक ने तब मुझे सीखने में मदद की थी, वह आज भी कभी-कभी post करता है
    खुद private server core compile करते हुए मैंने compile करना, SVN, और patch apply करना सीखा; शायद mage के Fireball से जुड़ा कोई bug था, लेकिन ठीक-ठीक याद नहीं

    • पुराने forums याद आते हैं तो nostalgia होता है
      आजकल लगता है कि internet के अच्छे हिस्सों का बड़ा भाग dopamine देने वाले social media apps और Reddit जैसे बंद forums ने replace कर दिया है
      शायद HN पर टिके रहने की वजह भी यही है कि यह पुराने forums की याद दिलाता है

  • “जो कोई arithmetic methods से random numbers बनाने की कोशिश करता है, वह निश्चय ही पाप की अवस्था में है। जैसा कई बार बताया गया है, random number जैसी कोई चीज़ नहीं होती। random numbers बनाने के केवल तरीके होते हैं, और कोई कठोर arithmetic procedure जाहिर तौर पर ऐसा तरीका नहीं है।” — John von Neumann

    • एक cryptographer के रूप में यह quote सचमुच बर्दाश्त करना कठिन है
      Neumann से मुझे शिकायत नहीं है, लेकिन इसे कोई बुद्धिमानी भरी कहावत की तरह फैलाने वाले लोग आम तौर पर गलत जानकारी ही पहुँचाते हैं
      context में यह अनावश्यक दार्शनिक मज़ाक जैसा है
      हमारे पास दशकों से तेज़ और भरोसेमंद cryptographic random number generators मौजूद हैं
      वे बहुत छोटे seed और arithmetic operations से भी सही तरह काम करते हैं, generated numbers किसी दूसरे सही random source से अलग नहीं पहचाने जा सकते और किसी भी उद्देश्य के लिए इस्तेमाल किए जा सकते हैं
      बहुत सारे लोग यह नहीं समझते, और “true random numbers” वाला snake oil बेचने वाली कंपनियाँ तक पैदा हो गई हैं

  • बेहद खराब random number generator का अच्छा उदाहरण Monster Hunter 3 Ultimate में है, और शायद अन्य titles में भी हो सकता है
    अच्छे loot पाने के लिए यह पूरी तरह exploitable था, और “charm table” भी बन गया था
    कुछ items के stats random generate होते हैं, लेकिन initial seed save file में stored होता है, इसलिए मिलने वाले items की range सीमित हो जाती है
    अगर किस्मत खराब हो, तो आप “cursed table” में फँस सकते हैं, जो असल में बहुत छोटे period वाला random number generator है, और फिर आप कभी भी maximum values नहीं पा सकते
    game को तोड़ देने लायक नहीं, लेकिन high-level play के लिए खराब है

  • मैंने auction house script लिखी थी
    वह सभी auctions scan करती थी, undervalued items खरीदती थी और फिर उन्हें दोबारा list करती थी
    अगर कोई और सस्ता list करता, तो मैं cancel करके उससे थोड़ा कम price पर फिर से list कर सकता था, और व्यावहारिक रूप से unlimited gold बन गया था

    • Goldman में काम करने वाले सचमुच नशे में लोगों से यह सुनने के बाद कि पैसा कैसे घूमता है, मैंने अपने छोटे भाई को समझाया, तो उसने जवाब दिया, “तो क्या IRS एक gold sink है?”
      “हम्म, सच कहूँ तो यह काफी अच्छा analogy है। फर्क यह है कि… उम्म… काफी अच्छा analogy है!”
    • यह मूल रूप से real-world high-frequency trading जैसा ही है
    • क्या आपने Auctioneer बनाया था? या Auctioneer जैसा ही कुछ था, लेकिन “industry standard” tool इस्तेमाल न करने का फैसला किया था?
    • जिज्ञासा है कि undervalued है या नहीं, यह कैसे तय किया?
    • क्या आप Auctioneer add-on के creator हैं? अगर हाँ, तो यह अब तक 10 साल से भी ज्यादा समय से सबसे लोकप्रिय WoW add-ons में से एक रहा होगा

  • “जब variables बदलते नहीं और constants स्थिर नहीं रहते”

    • दिलचस्प। यह गहरी जड़ों वाला meme लगता है
      https://www.theregister.com/2006/07/26/constants_are_not/
      “इस लेख के शीर्षक में programming की अनिश्चितताओं पर यह आह, ‘Variables Won't Constants Aren't’, मैंने पहली बार Creative Computing में पढ़ी थी, C बनने से कई साल पहले।”
      अगर कोई खास document है जिसे आप इस meme का canonical रूप मानते हैं, तो मैं उसे पढ़ना चाहूँगा