CAPTURINGBLUETOOTHTRAFFICINTHEWILD:PRACTICAL SYSTEMSANDPRIVACYIMPLICATIONS By WahhabAlbazrqaoe ADISSERTATION Submittedto MichiganStateUniversity inpartialoftherequirements forthedegreeof ComputerScience-DoctorofPhilosophy 2018 ABSTRACT CAPTURINGBLUETOOTHTRAFFICINTHEWILD:PRACTICALSYSTEMSAND PRIVACYIMPLICATIONS By WahhabAlbazrqaoe Bluetoothwirelesstechnologyistodaypresentinbillionsofsmartphones,mobilede- vices,andportableelectronics.WiththeprevalenceofpersonalBluetoothdevices,aprac- ticalBluetoothtrafsnifferisofincreasinginterestduetothefollowing.First,ithasbeen reportedthatatrafsnifferisanessential,day-to-daytoolforBluetoothengineersand applicationsdevelopers[4][14];andsecond,asthecommunicationbetweenBluetooth devicesisprivacy-sensitiveinnature,exploringthepossibilityofBluetoothtrafsniff- inginpracticalsettingsshedslightsintopotentialuserprivacyleakage.Todate,snif Bluetoothtrafhasbeenwidelyconsideredanextremelyintricatetaskduetowideband spreadspectrumofBluetooth,pseudo-randomfrequencyhoppingadoptedbyBluetooth atbaseband,andtheinterferenceintheopen2.4GHzband. Thisthesisaddressesthesechallengesbyintroducingnoveltrafsniffersthatcapture Bluetoothpacketsinpracticalenvironments.Inparticular,wepresentthefollowingsys- tems.(i)BlueEar,thepracticalBluetoothtrafsnifsystemonlyusinggeneral, inexpensivewirelessplatforms.BlueEarfeaturesanoveldual-radioarchitecturewhere twoinexpensive,Bluetooth-compliantradioscoordinatewitheachothertoeavesdropon hoppingsubchannelsinindiscoverablemode.Statisticmodelsandlightweightmachine learningtoolsareintegratedtolearntheadaptivehoppingbehaviorofthetarget.Our resultsshowthatBlueEarmaintainsapacketcaptureratehigherthan90%consistently indynamicsettings.Inaddition,wediscusstheimplicationsoftheBlueEarapproachon BluetoothLEsnifandpresentapracticalcountermeasurethateffectivelyreducesthe packetcapturerateofsnifferby70%,whichcanbeeasilyimplementedontheBluetooth masterwhilerequiringnotoslavedeviceslikekeyboardsandheadsets. And (ii)BlueFunnel ,thelow-power,widebandtrafsnifferthatmonitorsBluetooth spectruminparallelandcapturespacketinrealtime.BlueFunneltacklesthechallenge ofwidebandspreadspectrumbasedonlowspeed,lowcostADC(2Msamples/sec)to subsampleBluetoothspectrum.Further,itleveragesasuiteofnovelsignalprocessing algorithmstodemodulateBluetoothsignalinrealtime.WeimplementBlueFunnelpro- totypebasedonUSRP2devices.,weemploytwoUSRR2devices,eachis equippedwithSBXdaughterboard,tobuildacustomizedsoftwareradioplatform.The customizedSDRplatformisinterfacedtothecontroller,whichimplementsthedigital signalprocessingalgorithmsonapersonallaptop.Weevaluatethesystemperformance basedonpacketcaptureratesinavarietyofinterferenceconditions,mainlyintroduce bythe802.11-basedWLANs.BlueFunnelmaintainsgoodlevelsofpacketcapturerates inallsettings.Further,weintroducetwoscenariosofattacksagainstBluetooth,where BlueFunnelsuccessfullyrevealssensitiveinformationaboutthetargetlink. ACKNOWLEDGMENTS Theworkpresentedinthisthesiswouldnothavebeenpossiblewithoutthehelpand supportofalargegroupofpeopletowhomIowealotofgratitude.Firstandforemost,I amreallythankfulformyadvisorDr.GuoliangXingwhohasgivenmethistremendous opportunitytocomeandworkwithhim.Formorethanyears,hehassupportedme andworkedwithme.Frommyearlydays,despitemyunfamiliaritywithresearch,he encouragedmetotacklerealresearchproblemsandperformhighqualityresearch.Iam deeplyindebtedtoDr.Xingandhopetobeasgoodanadvisorwhenguidingmyown students. IamalsoreallygratefulforJunHuangwhowaslikeasecondadvisortome.Hehas supportedmeandguidedmethroughalotproblems.Hisdecisiontoworkwithmeon problemsrelatedtoBluetoothandWiFihaschangedandshapedmyentirePhDcareer.I trulyadmireandrespecthim. IwouldliketothankmysponsorIraqicultureofatWashingtonD.C.whooffered methisopportunityandsupportedmethroughallofmyPh.D.journey. IwouldliketothankDr.EricTorngandDr.Abdol-HosseinEsfahanian,fromthe departmentofComputerScienceandEngineering,fortheirhelpandsupport.Iwould liketothankDennisPhillipsforhisvaluablediscussions,comments,andadvisesabout electronicdevices.Dennisalsohelpedmetoprintelectroniccircuitsboards,whereI learnedhowtodesignprintedcircuits.Ihadgreatpleasureofworkingcloselyandrun iv discussionswithstudentsatgraduateschoolAlirezaAmeli,HusainKhalifeh,QiuChen, andMohammadMahdiMoazzami. Iwouldliketoexpressmyearnestgratitudetomyfamily,myparents,mywifeZainab Alkaabi,andmychildren,allofwhommadecountlessestosupportmeandgive methebestpossibleopportunityforeducation.Theyhavealwayssupporting,encourag- ing,lovingme. v TABLEOFCONTENTS LISTOFFIGURES ...................................... ix KEYTOABBREVIATIONS ................................. xii Chapter1Introduction ................................. 1 1.1Challenges......................................2 1.2Contributions....................................3 1.2.1TheBlueEarBluetoothSniffer.......................3 1.2.2TheBlueFunnelTrafSniffer.......................4 1.3OrganizationofThesis...............................5 Chapter2Background ................................. 6 2.1BluetoothBackground...............................6 2.1.1BluetoothPHYlayer............................6 2.1.2PhysicalChannelAccess..........................7 2.1.2.1BluetoothClassicHoppingProtocol..............8 2.1.2.2BluetoothLEHoppingProtocol................10 2.1.3BluetoothNetwork.............................11 2.1.4Encryption..................................12 2.1.4.1BluetoothLEEncryption....................12 2.1.4.2BluetoothClassic.........................13 Chapter3ReviewofRelatedWork .......................... 14 3.1SnifonBluetoothTraf............................14 3.1.1Narrowbandsniffers............................14 3.1.2Widebandsniffers..............................16 3.2CrackingBluetoothEncryption..........................17 3.3PotentialPrivacyLeakage.............................18 Chapter4BlueEar:APracticalBluetoothTrafSnifSystemBasedon BluetoothCompliantRadios ....................... 20 4.1Introduction.....................................20 4.2BlueEarOverview..................................22 4.2.1ObjectivesandChallenges.........................22 4.2.2SystemArchitecture............................23 4.3DesignofBlueEar..................................26 4.3.1ClockAcquisition..............................26 4.3.1.1BruteForceClockAcquisition.................26 4.3.1.2ProbabilisticClockMatching(PCM)..............28 4.3.1.3AcceleratingClockAcquisition.................29 4.3.2Subchannel.........................31 vi 4.3.2.1Packet-based.....................32 4.3.2.2SpectrumSensing-based...............34 4.3.2.3Hybrid.........................35 4.3.3SelectiveJamming.............................37 4.4Implementation...................................39 4.4.1Ubertooth-EndImplementation......................40 4.4.2ControllerImplementation........................41 4.5BlueEarPerformance................................42 4.5.1ExperimentalMethodology........................43 4.5.2SynchronizationDelay...........................44 4.5.2.1DelaybasedonPCMalgorithm................45 4.5.2.2DelaybasedonMLalgorithm.................45 4.5.3FastVaryingSpectrumContext......................47 4.5.4HiddenandExposedInterference....................48 4.5.5CrowdedSpectrum.............................51 4.5.6AmbientInterference............................52 4.6ImplicationsofBlueEar...............................52 4.6.1ImplicationsonBluetoothLEPrivacy..................52 4.6.2ImpactsonPrivacyBreach.........................54 4.6.2.1EavesdroppingonDataTraf.................55 4.6.2.2EavesdroppingonAudioTraf................56 4.6.3PracticalCountermeasure.........................57 4.7SummaryofChapter................................58 Chapter5BlueFunnel:EnablingLow-Power,WidebandSnifofBluetooth Traf ..................................... 59 5.1Introduction.....................................59 5.2BlueFunnelDesign.................................61 5.2.1ObjectivesandChallenges.........................61 5.2.2Systemarchitecture.............................63 5.2.2.1Analoganddownconversion............63 5.2.2.2Packetdetectionanddemodulation...............64 5.3Design........................................65 5.3.1BluetoothDemodulator..........................65 5.3.1.1DemodulatingBluetoothLEsignal...............66 5.3.1.2DemodulatingBluetoothClassicsignals...........68 5.4Implementation...................................71 5.5SystemPerformance................................73 5.5.1ExperimentalMethodology........................73 5.5.2Evaluation..................................74 5.5.2.1PacketCaptureRateinControlledSettings..........74 5.5.2.2PacketCaptureRateinPracticalEnvironment........75 5.6AttackScenarios...................................76 5.6.1SnifonPairingPhaseofBluetoothLE................77 5.6.2SnifonBluetoothMouseTraf...................78 vii 5.7SummaryofChapter................................80 Chapter6ConclusionandFutureWork ....................... 81 6.1Contributions....................................81 6.2Futurework,andConclusion...........................83 BIBLIOGRAPHY ....................................... 85 viii LISTOFFIGURES Figure2.1: AnillustrativeepresentsBluetoothClassicsubchannelsthatoverlapwith 802.11-basedchannelsintheopen2.4GHzISMband. .............7 Figure2.2: BluetoothmodulatedsignalbasedonGFSKmodulationscheme.Thee isadoptedfrom[51]. ...............................8 Figure2.3: Anillustrativeexampleoffrequencyhoppingchannelaccessscheme. .....9 Figure2.4: Anillustrativeexampleofadaptivefrequencyhoppingundertheeffectof 802.11-basedinterferenceinthe2.4GHzband. .................10 Figure3.1: NarrowbandsniffersutilizeBluetooth-compliantradiostocaptureBluetooth packets.Thisepresentsthreesamplesincluding(a)Ubertoothone,(b) TexasInstrumentCC2540USBDongleBluetoothLEsniffer,and(c)Bluefruit BluetoothLEsniffer. ...............................15 Figure3.2: WidebandsniffersutilizespecializedwidebandradiostomonitorBluetooth spectruminparallel.Thisepresentstwosamplesincluding(a)Frontline Sodorawidebandsniffer,and(b)EllisysBluetoothExplorer. ..........16 Figure4.1: Thedual-radioarchitectureofBlueEar.Componentsinthegrayareacomprise astandard-complianthopselectionkernel. ...................24 Figure4.2: Anillustrativeexampleofbruteforcesearchforclockacquisition. .......27 Figure4.3: Theeffectofsubchannelremappingonbruteforcesearchbasedonthesame exampleshowninFig.4.2. ............................28 Figure4.4: EstimationofapiconetclockbasedontheMLalgorithmandlossfunction L ( c i )= d i . .....................................31 Figure4.5: Runningexamplesofpacket-basedsubchannelfordataandvoice trafunderindifferentspectrumcontexts.Thepacket-basedcalcu- latesaprobabilityscorebasedonEq.(4.1)todeterminesubchannelstatus.A subchannelisasbadiftheprobabilityscoreisbelowthepr threshold. .....................................33 Figure4.6: Probabilitydensitiesofinterferencepowermeasuredoncleananddirtysub- channels. .....................................34 ix Figure4.7: Time-domainillustrationofrun-timetrainingofthespectrumsensing-based . .....................................36 Figure4.8: BlueEarprototypethatconsistsoftwoUbertooths[31]. .............39 Figure4.9: Clockacquisitiondelaywhensnifdataandaudiotrafindifferentspec- trumcontexts(characterizedbythepercentageofbadsubchannelsatthetar- getpiconet). ....................................44 Figure4.10: ClockacquisitiondelaybasedontheMLalgorithm,whichisevaluatedindif- ferentspectrumcontexts(characterizedbythepercentageofbadsubchannels atthetargetpiconet). ...............................46 Figure4.11: Subchannelaccuracyinfastvaryingspectrumcontext. ......47 Figure4.12: Packetcapturerateinfastvaryingspectrumcontext. ..............48 Figure4.13: Thegainofselectivejammingunderhiddeninterference. ...........48 Figure4.14: Packetcaptureratesincrowdedspectrumcharacterizedbythepercentageof badsubchannelsatthetargetpiconet. ......................49 Figure4.15: Packetcaptureratesunderexposedinterferencecondition. ...........49 Figure4.16: Subchannelaccuracyincrowdedspectrumcharacterizedbythe percentageofbadsubchannelsatthetargetpiconet. ..............50 Figure4.17: Subchannelaccuracyunderexposedinterferencecondition. ...51 Figure4.18: Packetcaptureratesundertheambientinterference:(a)differentlocations inanofbuilding(interferenceofalarge-scale802.11-basedWLANs);(b) differentdistances. ................................51 Figure4.19: Seriousnessofprivacyleakageevaluated:(a)standard;and(b)countermeasure. 55 Figure4.20: AudioqualityobservedbyBlueEar(withoutcountermeasure). .........56 Figure4.21: Audioqualityasthetargetimplementscountermeasure. ............57 Figure4.22: BlueEarpktcapturerates:standardandcountermeasure. ...........58 Figure5.1: BlueFunnelsystemarchitecture. .........................63 Figure5.2: FrequencydownconversionofBluetoothsignal. ................64 x Figure5.3: Bluetoothreal-timecomplexsignal. .......................65 Figure5.4: AnillustrativeexamplewherethecenterfrequencyofBluetoothtransmitter andBlueFunnelarematched. ..........................66 Figure5.5: AnillustrativeexamplewherethecenterfrequencyofBluetoothLEtransmit- terandBlueFunnelarenotmatched. ......................67 Figure5.6: AnillustrativeexamplewherethecenterfrequencyofBluetoothClassictrans- mitterandBlueFunnelarenotmatched. ....................69 Figure5.7: AprototypeofBlueFunnelsniffer,wherewebuiltacustomizedSoftwareDe- Radio(SDR)platformbasedontwoUSRP2devicesasshownin(a).The softwarecomponents,includingpacketheaderdetectorandBluetoothsignal demodulator,areimplementedontheLinux-basedLenovoT530laptopas shownin(b).TheUSRP2devicesaresynchronizedviaaMIMO-Cableand eachUSRP2isconnectedtothehost(Lenovolaptop)viaGigabitEthernetcable. 72 Figure5.8: PacketcapturerateachievedbyBlueFunnelundervariousinterferencecon- ditionsinacontrolledsetting. ..........................74 Figure5.9: PacketcapturerateachievedbyBlueFunnelatdifferentfromthetarget. ....75 Figure5.10: PacketcapturerateachievedbyBlueFunnelatdifferentlocationsinof Building. .....................................76 Figure5.11: BluetoothLEencryptionestablishmentparameters(markedwithred). ....77 Figure5.12: MousecoordinatesobtainedfromcapturedBluetoothpackets. .........79 xi KEYTOABBREVIATIONS AP AccessPoint AES AdvancedEncryptionStandard ADC AnalogtoDigitalConverter CCM CipherblockChainingMessageauthentication FCC FederalCommunicationsCommission FEC ForwardErrorCorrection ISM Industrial,andMedical CSR CambridgeSiliconRadio CRC CyclicRedundancyCheck DK DevelopmentKit DMA DirectMemoryAccess RAM RandomAccessMemory dBi Decibelsrelativetoanisotropicantenna dBm Decibel(referencedtomilliwatts) EDIV Encrypted GB GigaByte MB MegaByte KB KiloByte PHY PhysicalLayer SS SpectrumSensingbased SSD SolidStateDrive SVM SupportVectorMachine PCM ProbabilisticClockMatching ML MaximumLikelihood LE LowEnergy xii LNA LowNoise log Logarithm Msamples Millionsamples MSymbols MillionSymbols Mbps MegaBitPerSecond MOS MeanOpinionScore MIMO MultipleInputandMultipleOutput PSNR PeakSignaltoNoiseRatio SDR SoftwareRadio GFSK GaussianFrequency-ShiftKeying DPSK DifferentialPhase-ShiftKeying OFDM OrthogonalFrequencyDivisionMultiplexing FP FalsePositive FN FalseNegative RF RadioFrequency PC PersonalComputer PIN PersonalNumber Pkt Packet-based WLAN WirelessLocalAreaNetwork STK ShortTermsKey LTK LongTermsKey USRP UniversalSoftwareRadioPeripheral UHD USRPHardwareDriver USB UniversalSerialBus 10K 10000US$ SKDm SessionKeyforMaster IVm InitializationVectorforMaster sec MicroSecond msec Millisecond xiii Chapter1 Introduction RecentyearshavewitnessedthephenomenalpenetrationrateofBluetoothtechnologyin ourdailylives.About4billionBluetoothunitsareexpectedtobeshippedworldwidein 2018[15].Duetoit'sattractivefeatures,suchaslowcostandlowpowerconsumption, Bluetoothhasbecomethedefactowirelessconnectivityforwirelessaccessories,smart devicesincludingsmartphones,wearablesincludingsmartwatchesandtrackers, sensor-basedhealthcaresystems[57],consumerelectronicdevices,in-cartelematicsys- temslikeAndroidAuto[18]andCarPlay[5],andmanyotherapplications. WiththewidespreaduseofBluetoothtechnology,includingBluetoothClassicand BluetoothLowEnergy(LE) 1 ,snifBluetoothtrafcbecomesofincreasinginterestdue tothefollowing.First,apassiveBluetoothtrafsniffer/analyzerhasbecomeoneof theessential,day-to-daytoolforBluetoothengineersandapplicationdevelopers,asre- portedby[4][14].Second,asthecommunicationsbetweenBluetoothdevicesareprivacy- sensitiveinnature,anin-depthstudyonBluetooth'sresiliencetotrafsnifandpo- tentialprivacyleakagesbecomeimperative. Inthefollowing,wediscussthechallengesofsnifBluetoothtrafandintroduce ourcontributionstotacklethechallenges. 1 Inthisthesis,weuseBluetoothLEtorefertoBluetoothLowEnergyunlessotherwise 1 1.1Challenges SnifBluetoothtrafhasbeenconsideredanextremelyintricatetaskduetothefol- lowing, ( i) WidebandSpreadSpectrum. Bluetoothoperatesinthefree2.4GHzbandandde- severalsubchannelsthatspreadover80MHzofthespectrum.Therefore, asnifferwouldneedawidebandradiotomonitortheentirespectrumandcap- tureallBluetoothpacketsinrealtime.However,thiswidebandradiosolutionis challengingbecauseitrequiresahigh-speed(abouttwicethespectrum,according toNyquist-Shannonrate)analog-to-digital-converters(ADCs)tocaptureBluetooth signal.TheseADCsarecostly,powerhungry,andrequirehighcomputationalpower systemtosupportsuchhighsamplerate. ( ii) Pseudo-randomfrequencyhopping. AsBluetoothoccupiesonesubchannel,thatis1-2 MHz,atatimefordataexchange,asniffercouldemployalow-power,off-the-shelf Bluetooth-compliantradiotocapturedatapackets.Atthebaseband,however,Blue- toothadoptsfrequencyhoppingspreadspectrum,whichisachallengeforthiskind ofsniffers.Thatis,frequencyhoppingsequenceisknowntolegitimateBluetoothde- vicesbutnototherparties.Therefore,asniffercanlistenonanarbitrarysubchannel, andcapturepacketsthatarerandomlytransmittedonthatsubchannel.However, thenumberofpacketscapturedinthiswayrepresentsatinyportionofthetraf Moreover,Bluetoothsessionsmaylastforaveryshortperiodoftimeandinvolve onlytensofpackets. 2 ( iii) Interferenceinthecrowded2.4GHzband. Whencoexistingwithotherwirelessde- vicesinthecrawdad2.4GHzband,Bluetoothmayexperiencevariousinterference conditions,includinghiddenandexposedinterference,from802.11-basedWLANs andotherambientradios.Therefore,Bluetoothadoptsadaptivefrequencyscheme toadaptspectrumutilizationandimproveperformance.Totacklethesechallenges, asnifneedstolearnadaptivefrequencyhoppingbehavior,andprovidesome mechanismtonulltheinterferenceinthecaseofcollisionwithBluetoothpacketsin realtime. 1.2Contributions ThisthesistacklesthechallengesofsnifBluetoothtrafinpracticalenvironment. Thecontributionsofthethesisaresummarizedasfollows. 1.2.1TheBlueEarBluetoothSniffer Wepresentthedesign,implementation,andevaluationof BlueEar Œthepractical Bluetoothtrafsnifferthatconsistsonlyofinexpensive,Bluetooth-compliantradios. BlueEarfeaturesanovel dual-radioarchitecture ,wheretworadiosŒnamedas scout and snooper Œcoordinatewitheachotheronlearningthehoppingsequenceofindiscover- ableBluetooth,predictingadaptivehoppingbehavior,andhandlingcomplexinterference conditions.WeimplementedaprototypeofBlueEarforsnifthetrafofBluetooth Classic,whichoffersenhanceddataratesandamorecomplexhoppingprotocolthan BluetoothLE.TheprototypeemploystwoUbertooths[31]toimplementthescoutand thesnooper,andinterfacesthemtoacontrollerrunningonaLinuxlaptop.Extensive 3 experimentsresultsshowthatBlueEarcanmaintainapacketcaptureratehigherthan 90%consistentlyinpracticalenvironments,wherethetargetBluetoothnetworkexhibits diversehoppingbehaviorsinthepresenceofinterferencefromcoexisting802.11-based WLANs.Further,wediscussprivacyimplicationsofBlueEaronBluetoothsystemand proposeapracticalcountermeasureapproachthateffectivelyreducestheaveragepacket capturerateofasnifferto20%. 1.2.2TheBlueFunnelTrafSniffer Weintroducethedesign,implementation,andevaluationof BlueFunnel Œalow-power, widebandtrafsnifferthatmonitorsBluetoothspectruminparallelandcapturespacket inrealtime.BlueFunnelleverageslowspeedADCtosubsampleBluetoothspectrum, whichaddressesthechallengeofhigh-speedADC.Inparticular,BlueFunnelconsistsof twomaincomponents,including, (i) asoftwareradio(SDR),thatintegratesa widebandradio,andalow-speedADC.TheADCisusedtosubsampleBluetoothspec- trumbasedon2Msamples/sec,whichisbelowtheNyquist-Shannonrate;and (ii) a controller,thatimplementsdigitalsignalprocessingpackages,whichareresponsiblefor detecting,demodulating,andanalyzingBluetoothpacketsinrealtime.Weimplement BlueFunnelprototypebasedonUSRP2devices.,weutilizetwoUSRR2de- vices,eachisequippedwithSBXdaughterboard,tobuildacustomizedsoftwareradio platform.ThecustomizedSDRplatformisinterfacedtothecontroller,whichimplements thedigitalsignalprocessingalgorithmsonapersonallaptop.Weevaluatethesystem performancebasedonpacketcaptureratesinvarietyofsettings.,weeval- uatedthesysteminacontrolledsetting,whereweintentionallyintroduce802.11-based trafasaformofinterferenceonoverlappedBluetoothsubchannels.WetestBlueFunnel 4 whenthereisnointerference,25%and50%ofthesubchannelsareinterferedwith802.11- basedtrafrespectively.Moreover,weevaluatethesysteminanofbuilding,where dynamicinterferenceconditionsareintroducedbyenterprise802.11-basedWLANs.In allsettings,BlueFunnelmaintainsgoodlevelsofpacketcapturerates.Further,weintro- ducetwoscenariosofattacksagainstBluetooth,whereBlueFunnelsuccessfullyreveals sensitiveinformationaboutthetargetlink. 1.3OrganizationofThesis Therestofthisthesisisorganizedasfollows.Chapter2introducesthebasiccharac- teristicsofBluetoothsystem,anddiscussesthechallengesofsnifBluetoothtraf Chapter3providesareviewofrelatedworks.Chapter4presentsBlueEar,theprac- ticalsystemthatconsistsofonlyinexpensive,Bluetooth-compliantoff-the-shelfradios. Chapter5introducesBlueFunnel,anovellow-power,widebandBluetoothtrafsniffer. Chapter6concludesthisthesisanddiscussesfuturework. 5 Chapter2 Background Inthischapter,wepresentthebackgroundforthethesisincludingthebasiccharacteristics ofBluetoothbaseband. 2.1BluetoothBackground Inthissection,weintroduceageneralbackgroundaboutBluetoothphysicallayer,includ- ingmodulationscheme,frequencyhoppingprotocol,encryptiontechniquesadoptedby Bluetoothsystem,includingBluetoothClassicandBluetoothLE. 2.1.1BluetoothPHYlayer Bluetoothoperatesinthefree 2 . 4 GHzISMband.Bluetoothclassic 79 adjacent subchannels,whereeachsubchanneloccupies1MHzofbandwidth,asillustratedinFig. 2.1.Ontheotherhand,BluetoothLE 40 adjacentsubchannels,whereeachsub- channeloccupies 2 MHzofbandwidth.Bluetoothsubchannelsoccupyabout 80 MHzof thespectrumstartingfrom 2402 MHzupto 2480 MHz. Atthebaseband,Bluetoothadoptsthesymboltransmissionrateof 1 MillionSym- bols/sec,whereeachsymbolismodulatedbasedonGaussianFrequency-ShiftKeying (GFSK)modulationscheme.Thetransmittedsignalcanbedescribedasacosinewave 6 Figure2.1: AnillustrativeepresentsBluetoothClassicsubchannelsthatoverlapwith802.11- basedchannelsintheopen2.4GHzISMband. [53], x ( t )= Acos ( 2ˇ ( f c + ) t ) (2.1) where f c isthecarrierfrequency, isafrequencyshiftintroducedbytheGFSKmod- ulation,and 0<<0 . 5 represents' 1 ',while - 0 . 5<<0 represents' 0 ',asdepictedin Fig.2.2.ThereisaspecialcaseforBluetoothClassictoenhancedatarates,whereDiffer- entialPhase-ShiftKeying(DPSK)modulationschemeisalsosupported.However,this modulationisbeyondthescopeofthisthesisandmaybeconsideredasafuturework. 2.1.2PhysicalChannelAccess Atthebaseband,Bluetoothutilizes frequencyhoppingspreadspectrum toaccesssubchan- nels.Thatis,thecarrierfrequency f c isswitchedeveryaperiodoftime.Inthefollowing, weintroduceageneraldescriptionaboutthehoppingprotocolsofBluetoothClassicand BluetoothLE,respectively. 7 Figure2.2: BluetoothmodulatedsignalbasedonGFSKmodulationscheme.Theeis adoptedfrom[51]. 2.1.2.1BluetoothClassicHoppingProtocol InBluetoothClassic,thecarrierfrequency f c isswitchedevery 625 sec,resultingina maximumhoppingrateof1600hops/sec,asdepictedinFig.2.3.Thecarrierfrequency iscalculatedas f c = 2402 + k MHz,where k = 0 , 1 , 2 ,..., 78 isthesubchannelindex.Now thequestionishowtocalculate k ?Thesubchannelindexiscalculatedintwodifferent waysbasedonthetwophysicalchannelbyBluetoothClassic.,there aretwotypesofphysicalchannelfordatacommunication,including, ( i) Basicchannel .Ineachhopofthebasicchannel,thesubchannelindexiscalculated by H ( A , c ) ,where H ( ) denotesthebasichopselectionkernelbytheBlue- toothstandard[47], A isthepiconetaddress(i.e.theMACaddressofthepiconet 8 Figure2.3: Anillustrativeexampleoffrequencyhoppingchannelaccessscheme. master),and c isthepiconetclock.InBluetoothClassic,thepiconetclockisa27-bit logiccounterthattickseveryhop.Becausepiconetclockwrapsaroundevery 2 27 ticks,thebasicchannelrepeatsitselfevery134,217,728hops,whichtakesapproxi- mately24hours.Inotherwords,thebasicchannelcanbecharacterizedbya basic hoppingsequence anda hoppingphase .Thebasichoppingsequence,whichisdeter- minedbythepiconetaddress,iscomposedof 2 27 subchannelindices f i 0 ,..., i 2 27 - 1 g , where i c = H ( A , c ) .Thehoppingphase,whichisdeterminedbythepiconetclock,is theindexofthecurrenthop. ( ii) Adaptedchannel .Operatinginthefree2.4GHzISMband,Bluetoothmaycoexistwith otherwirelessdevicesonoverlappedfrequencies.Therefore,Bluetoothperforms adaptivehoppingwherethebasicchannelisfrequentlytoadaptspectrum use.Theadaptationisguidedbya subchannelmap ,whichsubchannelsas goodandbadbasedoninterferenceconditions.Whenthesubchannelselectedina hopisbad,a remap functioniscalledtocomputeapseudo-randomindex i based onpiconetaddressandclock.Thebadsubchannelisthenreplacedbythe i -thgood subchannel. 9 Figure2.4: Anillustrativeexampleofadaptivefrequencyhoppingundertheeffectof802.11- basedinterferenceinthe2.4GHzband. Fig.2.4showsanillustrativeexampleofadaptivefrequencyhopping,whereBlue- toothavoidsinterferedsubchannels(gray).Althoughadaptivehoppingisthe defacto schemeusedbyoff-the-shelfBluetoothdevices,theBluetoothstandarddoesnotspecify theimplementationofsubchannelresultingindifferentadaptivehopping behaviorsacrossdevicesmanufacturedbydifferentvendors. 2.1.2.2BluetoothLEHoppingProtocol BluetoothLEtwotypesofphysicalchannel,namely (i)advertisement ,and (ii)con- nection .Foradvertisement,therearethreesubchannels,namely37,38,and39,where BluetoothLEoperatesinaconnectionlessmode.Thatis,BluetoothLEutilizestheadver- tisementsubchannelstobroadcastinformationforotherBluetoothLEdevices.Further, thethreesubchannelsmaybeusedtoinitiateconnections.Forconnectionstate,Bluetooth LEutilizestheremaining37subchannelstoestablishdataconnectionsbetweenBluetooth LEdevices.TheconnectionstateofBluetoothLEisbasedonconnectionevents, whereaneventrepresentsashortsessiontoexchangedatapackets.Foreachevent,Blue- toothLEswitchestoanewsubchannel. 10 SimilartoBluetoothClassic,BluetoothLEa basic and adaptive hoppingschemes. Forthebasicchannelhopping,thecarrierfrequency f c iscalculatedas f c = 2402 + 2k MHz,where k = 0 , 1 , 2 ,..., 39 isthesubchannelindex.Theindexiscalculatedbasedon K ( c i , inc ) ,where K ( . ) isthehopselectionkernel,and c i istheindexofcurrentsubchannel. Thesubchannelindex c i isinitializedtozerofortheconnectionevent.Therefore, thehoppingsequencerepeatswhenevertheindexbecomes c i = 0 [46].Duringpairing phase(i.e.connectionestablishment),themasterconnectionpa- rameters.Thisincludes (i) connectionintervalŒamultipleof 1 . 25ms rangingfrom 7 . 5ms to 4 . 0s thattheeventlifetime; (ii) transmissionwindowsizeŒamultipleof 1 . 25ms thatthesizeoftransmitwindow,i.e.packetsize;and (iii) hopincrement inc Œa randomvaluerangesfrom5to16. Theadaptivechannelisbasedona subchannelmap thattheconnec- tionsubchannelsintogoodandbad.Whenabadsubchannelisselectedbytheselection kernel K ( c , inc ) ,aremappingprocedureisinvokedtocalculatea remappedindex .Themas- termaintainsthesubchannelmapanditslave(s)aboutanyupdates[46]. 2.1.3BluetoothNetwork Bluetoothnetworksemployamaster-slavestructurecalleda piconet .Thedevicethathas theleastcomputationandpowerconstraintsisusuallyselectedasthemastertomanage communication.Otherdevicesareslaves.BluetoothpiconetsusetheMACaddressofthe masterdeviceasthe piconetaddress .Alldevicesfromthesamepiconetaresynchronized tothe piconetclock Œaclocksignalgeneratedbythemaster. Indiscoverablemode. Whenestablishingthepiconet,Bluetoothdevicesauthenticate eachotherthrougha pairing process.Toenhanceprivacy,Bluetoothpiconetscanbeput 11 inindiscoverablemodetohidekeytechnicalparametersfromunpaireddevices.These parametersŒincludingpiconetaddress,piconetclock,andsubchannelmapŒdetermines hoppingbehavior.Althoughrecentstudyhasdemonstratedthepossibilityofextract- ingpiconetaddressfrompacketpreambles[49],aBluetoothpacketsniffercannothop followingthetargetunlessitacquiresallhiddenparameters. 2.1.4Encryption 2.1.4.1BluetoothLEEncryption Topreserveuser'sprivacy,BluetoothLEemploysAESencryptionŒapopularsymmetric- keyencryptionalgorithm.Thismeansthepiconetmasterandslave(s)mustsharethe sameencryptionkey,thatisknownasLongTermKey(LTK),toestablishencryption session.KeydistributionmechanismofBluetoothLEisdifferentfromthatadoptedby BluetoothClassic;thisisbecauseofcomputationalandstoragelimitationsoflowpower BluetoothLEslaves.UnlikeBluetoothClassic,whichemploysSecureSimplePairing (SSP)forkeyagreement,aBluetoothLEmastergeneratesanddistributesLTKasen- cryptedmessage,basedonatemporarykeyakaShortTermKey(STK),tootherslaves. NowtodecrypttheLTK,allpiconetparticipantsneedstoregeneratetheSTK.Bluetooth LEslavesbaseonsomeseedsandrandomnumbersprovidedbythemasterdevice.Un- fortunately,theseseedsaresentovertheairasplaintext.Asaresult,aneavesdropper, whocancapturepairingphaseofBluetoothLE,maybeabletodetermineLTKand,hence, compromiseBluetoothLEprivacy[6][7][8][12][36][43][45]. 12 2.1.4.2BluetoothClassic AscommunicationofBluetoothdevicesisprivacy-sensitiveinnature,BluetoothClassic employs E 0 Œasymmetric-keystreamcipheralgorithmŒtoencryptuser'sdata.Unfortu- nately,recentstudieshaverevealedmanycriticalofthisencryptionscheme[55][56] [13][38].Inparticular,itisshownthatBluetoothissubjecttoseveralpracticalattacksthat cancircumvent,compromise,orevencrackthelink-layerencryption,leadingtopotential userprivacybreach[13][56]. 13 Chapter3 ReviewofRelatedWork Despitethewell-documentedofBluetoothencryption,snifBluetoothtrafhas beenwidelyconsideredanextremelyintricatetask.Thismainlyduetowidebandspread spectrum,pseudo-randomfrequencyhoppingemployedbyBluetoothatbaseband,and presenceofinterferenceintheopen2.4GHzband,whichismainlyintroducedby802.11- basedWLANs.Inthischapter,wereviewrelatedworkfromtheliterature,whichincludes Bluetoothsniffers,cryptanalysisofBluetoothencryption,andpotentialprivacyleakage inthelightofsuccessfultrafsnif 3.1SnifonBluetoothTraf Inthissection,wereviewBluetoothtrafsniffers,highlighttheirdrawbacks,andcom- pareourpracticalsystems,namelyBlueEarandBlueFunnel,thataddress thechallengesandimprovetrafsnifperformance.Bluetoothtrafsnifferscanbe categorizedintotwomainclassesincluding: 3.1.1Narrowbandsniffers TosniffonBluetoothtrafnarrowbandsniffersemployBluetooth-compliantradiosto captureBluetoothtrafFig.3.1presentssamplesofnarrowbandBluetoothsniffers. 14 (a)Ubertoothone. (b)TexasIns.CC2540Dongle. (c)BluefruitBluetoothLESniffer. Figure3.1: NarrowbandsniffersutilizeBluetooth-compliantradiostocaptureBluetoothpackets. Thisepresentsthreesamplesincluding(a)Ubertoothone,(b)TexasInstrumentCC2540USB DongleBluetoothLEsniffer,and(c)BluefruitBluetoothLEsniffer. ThereexistseveralproprietaryandopensourcesystemsforsnifBluetoothtrafFor example,theeofafewBluetoothchipsetsallowtheradiotoreportpacket-level diagnosisbyworkinginsnifmode[1][24][33].However,thesnifdevicemust pairwiththetarget,whichmakesitincapableofpassivesnif Recently,severalproprietarylow-costBluetoothpacketsniffers[23][44][2][34]have beenproposedbasedoninexpensive,BluetoothcompliantBluetoothplatform.Similarly, lowcost,opensourcesniffers[31][44]havebeendevelopedbasedonUbertooth[31] Œanopen-sourceBluetoothdevelopmentplatform.In[50],atrafsnifferisdevel- opedbasedonGNURadio/USRPplatform.However,existinglow-costsniffers,includ- ingUbertooth-basedone,areexclusivelydesignedforsnifBluetoothtrafinbasic hoppingmode.Inthecrowded2.4GHzband,Bluetoothrarelyhopsinbasichopping modebecauseoftheinterferencefromcoexistingwirelessdevices,especiallythepreva- lent802.11basedWLANs[17][28][54][20].Asaresult,existinglow-costsnifferssuffer prohibitivelypoorsnifperformanceinpracticeduetothemispredictionofadaptive hoppingbehavior,aswellasexcessivepacketcorruptionscausedbyinterference. 15 (a)SodorawidebandSniffer. (b)BluetoothExplorer. Figure3.2: WidebandsniffersutilizespecializedwidebandradiostomonitorBluetoothspectrum inparallel.Thisepresentstwosamplesincluding(a)FrontlineSodorawidebandsniffer,and (b)EllisysBluetoothExplorer. ComparedwithexistingUbertooth-basedsystems,BlueEarisdesignedforsnif Bluetoothtrafinpracticalenvironmentswhereboththesnifferandthetargetmaysuf- ferfromintensiveinterferencefromcoexistingwirelessdevices.Toachievethisgoal,we addressthekeychallengesposedbytheindiscoverablemodeofBluetooth,thevendor- dependentadaptivehoppingbehavior,andthedifinmaintainingconsistentsniff- ingperformanceinthecrowded2.4GHzband.Inaddition,weidentifyvariouscritical issuesinUbertoothethatdegradeitsperformanceduringfrequency hopping,andpresentsolutionstoaddresstheseWenotethatalthoughourproto- typeisdevelopedbasedonUbertooth,thedesignofBlueEarisplatform-independent andcanbeeasilyportedtoothersystems. 3.1.2Widebandsniffers WidebandtrafsniffersemployawidebandradiostomonitortheentireBluetoothspec- trumatthesametime.Fig.3.2showsexamplesofwidebandBluetoothsniffers.There areafewproprietaryBluetoothsniffersdesignedfortestingandprotocolanalysis[27] 16 [14].Thesesniffersutilizespecializedradiostomonitorallsubchannelsinparallelwhich makesthemextremelycostlyandpowerhungry.Forinstance,protocolanalyzersman- ufacturedbyTeledyne[27]cost$10kto$25Kperunit.Moreover,thesesniffersrequire explicitpairingwiththetargetBluetooth,whichmakesitimpossibletosniffonBluetooth trafpassively. Incomparisonwiththeabovesystems,BlueFunnelisdesignedasapassivetrafsnif- ferthatisbasedonwideband,low-power,inexpensivedevicesalongwithasuitofdigital signalprocessingmethodstocaptureBluetoothtrafinthewild.Moreover,BlueFunnel incursnodelayandnopacketlossasitrequiresnostatisticallearningphase. 3.2CrackingBluetoothEncryption BluetoothClassic employs E 0 Œatwo-levelstreamcipherbasedon128-bitlinkkeyŒto encryptpacketpayloads.Thelinkkeyisestablishedthrough pairing ,whereBluetooth devicesauthenticateeachotherusingasecretPIN.Intheliterature,studieshaverevealed manycriticalofthisencryptionscheme[55][56][13][38][37][40][11]. Inparticular,severalstudieson E 0 cryptanalysishaveshownthatthe128-bitlinkkey of E 0 isconsiderablyweakerthanwhatisoriginallyintended[55][56][37].Theencryp- tionkeycanbecrackedwith 2 27 onlineoperationsand 2 21 . 1 ofoperationsinsteadof 2 128 .,giventheheadersof 2 22 . 7 Bluetoothpackets,theattacktakesafewsec- ondstorestorethetargetencryptionkey.SuchattackisimplementedonasinglecorePC andrequires4MBRAMofmemory.Furthermore,theeffectivesecurityofthelinkkey willfurtherdegradewhenapacketsnifferisemployedbytheattacker. 17 3.3PotentialPrivacyLeakage InthelightofsuccessfultrafsnifweexplorepotentialprivacyleakagesofBlue- toothsystem,including, (i)CrackingBluetoothencryption. Bluetoothclassicemploys E 0 Œatwo-levelstreamcipher basedon128-bitlinkkeyŒtoencryptpacketpayloads.Recentstudieson E 0 cryptanal- ysisshowsthatthe128-bitlinkkeyof E 0 isconsiderablyweakerthanwhatisoriginally intended[55][56][37].Theencryptionkeycanbecrackedwith 2 27 onlineoperationsand 2 21 . 1 ofoperationsinsteadof 2 128 .,giventheheadersof 2 22 . 7 Bluetooth packets,theattacktakesafewsecondstorestorethetargetencryptionkey.Therefore,the effectivesecurityofthelinkkeywillfurtherdegradewhenapacketsnifferisemployed bytheattacker.Moreover,duetocomputationandpowerconstraints,manyBluetooth peripheralsincludingmostBluetoothmicemanufacturedbymajorvendors,likeLog- itech[29],donotsupportencryption,leadingtouserprivacybreach. (ii)Privacyleakagebasedonpatterns. WithoutthepainofcrackingBluetoothencryp- tion,previousstudiesdemonstratethepossibilityofBluetoothprivacybreachbyobserv- ingtrafpatterns.Forinstance,thetrafpatternofpopulartrackersisfoundto bestronglycorrelatedwiththeuser'sactivity,makingitpossibletotrackusergaitand identity.Asaresult,apassivetrafsniffercanuncoverimportantprivateinformation abouttheuser,evenwithoutdecryptingpacketpayloads[13]. (iii)Leakageofencryptionkey. BluetoothLEemploysAES-CCMblockcipherŒapopular symmetric-keyencryptionalgorithmŒtodecryptpacketspayload.Toestablishanen- cryptedsession,thepiconetmastersharesaLongTermKey(LTK)withslave(s).The keydistributionmechanismofBluetoothLEisdifferentfromthatadoptedbyBluetooth 18 Classic,duetocomputationalandstoragelimitationsoflowpowerslaves.Inpractice, themastergeneratesanddistributesLTKasencryptedmessagestootherslaves.The masterencryptsLTKbasedonatemporarykeythatisknownasShortTermKey(STK). Unfortunately,BluetoothLEsendsSTKovertheairasplaintext.Therefore,asuccess- fuleavesdroppingonBluetoothLEpairingphasecouldpotentiallyleadtodetermining LTK;and,hence,compromiseBluetoothLEprivacy[8][12][36].Furthermore,astudyon privacyofZigBeenetwork[43]demonstratesthefeasibilityofcircumventingAES-CCM encryptionwithouttheneedtoknowlinkencryptionkey.Although,thestudyconsiders ZigBeeencryption,theproposedmethodscanalsobeappliedtoBluetoothLEasboth ZigBeeandBluetoothLEemploytheAES-CCMblockcipher. 19 Chapter4 BlueEar:APracticalBluetoothTraf SnifSystemBasedonBluetooth CompliantRadios 4.1Introduction Inthischapter,weexplorethefeasibilityandprivacyimplicationsofsnifBluetooth trafinpracticalenvironments.UnlikepriorBluetoothtrafsniffersthatrelyonspe- cializedpower-hungrywidebandradios,oursnifsystemconsistsofonlycommodity Bluetooth-compliantradios.Ourmajorcontributionistwo-fold. TheBlueEarsystem. Wepresentthedesign,implementation,andevaluationof BlueEar ŒthepracticalBluetoothtrafsnifferthatconsistsonlyofinexpensive,Bluetooth- compliantradios.BlueEarfeaturesanovel dual-radioarchitecture ,wheretworadiosŒ namedas scout and snooper Œcoordinatewitheachotheronlearningthehoppingsequence ofindiscoverableBluetooth,predictingadaptivehoppingbehavior,andhandlingcom- plexinterferenceconditions.,thescouthopsoverallBluetoothsubchannels tosurveyinterferenceconditionsandmonitorsthetarget'spackettransmissions.Byfus- ingthesemeasurements,BlueEarusesaprobabilisticclockmatchingalgorithmtodeter- 20 minethebasichoppingsequence,andthenintegratesstatisticalmodelsandalightweight machinelearningalgorithmtopredicttheadaptivehoppingbehavior,whichallowsthe snoopertohopfollowingthetarget.Tomaintainreliablesnifperformanceincomplex interferenceconditions,thescoutrunsaselectivejammingalgorithm,whichmanipulates thehoppingofthetargettomitigatetheimpactsofinterference.Wehaveimplemented aprototypeofBlueEarforsnifthetrafofBluetoothClassic,whichoffersenhanced dataratesandamorecomplexhoppingprotocolthanBluetoothLE.Ourprototypecan beexpendedtosniffonBluetoothLEtrafTheprototypeemploystwoUbertooths[31] toimplementthescoutandthesnooper,andinterfacesthemtoacontrollerrunningon aLinuxlaptop.WeidentifycriticalissuesinUbertoothethatseverelydegrades itsperformanceduringfrequencyhopping,andpresentnovelsolutionstoaddressthese ExtensiveexperimentsresultsshowthatBlueEarcanmaintainapacketcapture ratehigherthan90%consistentlyinpracticalenvironments,wherethetargetBluetooth networkexhibitsdiversehoppingbehaviorsinthepresenceofinterferencefromcoexist- ing802.11basedWLANs. Privacyimplications. WediscusstheimplicationoftheBlueEarsystemonBluetooth privacy.Moreover,weevaluatetheperformanceofBlueEarwheneavesdroppingonau- diotrafwhichisknowntobeextremelysensitivetopacketloss.Weshowthatthe packetcapturerateachievedbyBlueEartranslatestoahighaudioqualitywithamean opinionscore(MOS)of3.5,whichistranslatedinto˚Fair'and˚Good'fromthelistener's perspective.Furthermore,wepresentapracticalcountermeasure,thatcanbeeasilyim- plementedintheuser-spacedriveroftheBluetoothmasterdevice,whilerequiringno toexistingslavedeviceslikekeyboardsandheadsets.Thecountermeasure 21 effectivelyreducesthepacketcapturerateofthesnifferto20%,anddegradestheMOSof eavesdroppedaudioto1.5,whichisbetween˚Bad'and˚Poor'. Therestofthechapterisorganizedasfollows.Wepresentsystemoverviewandar- chitectureinsection4.2.Insection4.3,wediscussBlueEarsystemdesignindetail.Eval- uationofBlueEarsystemperformanceispresentedinsection4.5.Wediscusstheimpacts ofBlueEaronprivacybreachforBluetoothsystem,includingBluetoothLE,insection4.6. Section4.7concludesthechapter. 4.2BlueEarOverview 4.2.1ObjectivesandChallenges WestudyBluetoothprivacybyexploringthefeasibilityofsnifBluetoothtrafin practicalenvironments.Tothisend,BlueEarisdesignedasa passive trafsnifferthat leveragesgeneral,inexpensivewirelessplatformtocaptureBluetoothpacketswithout pairingwiththetargetpiconet.Toachievethisgoal,wetacklethefollowingchallenges. ( i) Secrethoppingphase .Inindiscoverablemode,thepiconetclockthatindicatesthe hoppingphaseishiddenfromBlueEar.Inadaptivehoppingmode,determiningthe hoppingphaseisparticularlychallengingbecausethebasichoppingsequenceofthe targetissubjecttofrequent ( ii) Vendor-dependentadaptivehopping .TheadaptivehoppingofBluetoothisguidedby asubchannelmap,whichsubchannelsasgoodandbadbasedondynamic interferenceconditions.However,theBluetoothstandarddoesnotspecifytheim- plementationofsubchannelresultinginvendor-dependentimplemen- 22 tation,whereBluetoothchipsetsmanufacturedbydifferentvendorsmayhopover differentsubchannelseveninthesamespectrumcontext. ( iii) Interferenceinthecrowded2.4GHzband .Whencoexistingwithotherwirelessde- vices,BlueEarmayexperiencehiddenandexposedinterference.WhenanRFsignal thatinterfereswiththetargetistooweaktobemeasuredatBlueEar,thespectrum contextsobservedbyBlueEarandthetargetmaydiffer,makingitdiftopre- dictadaptivehoppingbehavior.WhenanRFsourceinterfereswiththetargetbut BlueEar,degradationofsnifperformancemayoccur.Whileautho- rizeddevicescanmaintainpacketreceptionperformancebycoordinatingtheirhop- ping,designedasapassivesniffer,BlueEarcannotcoordinatewiththetarget,which mayleadtosubstantialpacketcorruptions. 4.2.2SystemArchitecture Insteadofusingspecializedradiotomonitorallsubchannelsinparallel,BlueEartackles theabovechallengesbasedonasimple dual-radioarchitecture thatconsistsoftwoinex- pensive,Bluetooth-compliantradios.ThetworadiosŒnamedas scout and snooper Œare interfacedtoacontroller,whichemploysasuiteofnovelalgorithmstocoordinatethe tworadios,gluingthemasapowerfulpassivetrafsniffer.Fig.4.1illustratesthear- chitectureofBlueEar.,theworkingofBlueEarcanbedividedintothe followingsteps. ( i) T Whenmultiplepiconetscoexistinthesameenvironment,BlueEar separatestheirtrafbasedonthepiconetaddressofcapturedpackets. cally,thepreambleofeachBluetoothpacketcarriesasynchronizationword,which 23 Figure4.1: Thedual-radioarchitectureofBlueEar.Componentsinthegrayareacomprisea standard-complianthopselectionkernel. isderivedfromthepiconetaddressusinganencodingfunctionbythestan- dard[47].BlueEaremploysthebruteforcealgorithmproposedin[49]toextractpi- conetaddressfromthesynchronizationword,andthenoutthepacketswhose piconetaddressmismatchesthetargetpiconetaddressbytheBlueEaruser. ( ii) Basicchannelacquisition. Toacquirethebasicchannelofthetargetpiconet,thescout listensonanarbitrarysubchanneltomonitorthetarget'spackettransmissions.Af- terextractingpiconetaddressfrompacketpreamble,BlueEarderivestheentireba- sichoppingsequence,andthenreversesthepiconetclockusinganinterferencere- silient,probabilisticclockmatchingalgorithm.,thereceivingtimesof capturedpacketsarecomparedwiththebasichoppingsequenceatdifferenthop- 24 pingphases,untilacorrectphaseisfound.Theacquiredpiconetaddressandclock arethenfedtoastandard-compliantbasichopselectionkerneltocomputethebasic channel. ( iii) Adaptedchannelacquisition. Toacquiretheadaptedchannel,BlueEarneedstopredict howthetargetreactsindynamicspectrumcontext.Tothisend,thescouthopsover allsubchannelsontheacquiredbasicchanneltosurveyinterferenceconditions,and monitorspackettransmissionstoinferthetarget'ssubchannelutilization.Byfus- ingthesemeasurements,BlueEartrainsasubchannelatrun-time,which accuratelyderivesthetarget'ssubchannelmapdespitevendor-dependentadaptive hoppingbehaviorandthepossibledisparitybetweenthespectrumcontextsofthe scoutandthetarget.Thesubchannelmapisthenfedtoastandard-compliantadap- tivehopselectionkernelforcomputingtheadaptedchannel. ( iv) Interferenceavoidance. Thesnooperhopsfollowingthetargetontheadaptedchan- neltosnifftrafBlueEarhandlescomplexinterferenceinthecrowded2.4GHz bandusingaselectivejammingalgorithm.,alossdetectorisemployed tomonitorthesnifngperformanceofallsubchannels.Whensubstantialpacketcor- ruptionsaredetectedonasubchannel i ,thescoutdeliberatelygeneratesinterference on i whilethetargetvisits i duringhopping.Becauseofadaptivehopping,thetarget willbedrivenawayfromlossysubchannelswhereBlueEarobservespoorsnif performance.Theobjectiveistomanipulatethetarget'shoppingtoenforceimplicit coordination. 25 4.3DesignofBlueEar Inthissection,wepresentthedesignofkeyBlueEarcomponentsindetail. 4.3.1ClockAcquisition Inthefollowing,wesometerminologyandpresentkeyconceptsofclockacquisi- tion. 1Basichoppingsequence =( i 0 ,.., i c ,.., i N ) isann-tupleofintegers i 2 f 0 ,.., 78 g thatrepresentssubchannelindex, c referstothepiconetclock,i.e.hoppingphase, and N = 2 27 - 1 . 2Observedhoppingpattern P = f p 0 , p 1 ,.., p n g isasetofcapturedpackets, whereapacketisbasedonsystemtime-stampatreceptiontime. Next,weintroduceourbasicideaofreversingthepiconetclock,whichinvolvesthree fundamentalalgorithms,including,reversingthepiconetclockwhenthetargethops inthebasicmode;second,wepresentaprobabilisticmatchingapproachtodetermine thepiconetclockinthepresenceofinterference.And,weintroduceamaximum- likelihood(ML)basedalgorithm,whichacceleratesclockacquisitionand reducesclockacquisitiondelay. 4.3.1.1BruteForceClockAcquisition Becausetheentirehoppingsequence isknownafterthepiconetaddressisextracted frompacketpreamble[49],itispossibletoreversethepiconetclock c throughasimple bruteforcesearch,whichcomparesanobservedhoppingpatternwiththeentirehopping sequenceatallphasestosearchforamatch.Fig.4.2showsanillustrativeexample. 26 Figure4.2: Anillustrativeexampleofbruteforcesearchforclockacquisition. Atthebeginning,thescoutlistensonasinglesubchanneltomonitorthetarget'spacket transmissions.AsshowninFig.4.2,thescoutlistensonsubchannel2wherethreepackets arecaptured,which P .Thereceivingtimesofthesepacketscomposeahopping patternthatdescribeshowthetargetvisitsthemonitoredsubchannel.AsshowninFig. 4.2(c)and(d),BlueEarthencomparestheobservedhoppingpatternwiththeentirebasic hoppingsequenceatallphases.Amatchisfoundatclock34. Beforecapturingasufnumberofpackets,theobservedhoppingpatternmay happentomatchthebasichoppingsequenceatmultipleclockvalues,resultinginclock ambiguity.Becausethebasichoppingsequenceispseudo-random,probabilitythatan observedhoppingpatternthatcomprises n packetsmatchesthebasichoppingsequence atanarbitraryclockcanbecomputedas 1 79 n .Therefore,clockambiguitydecreasesasthe numberofcapturedpacketsincreases. 27 Figure4.3: Theeffectofsubchannelremappingonbruteforcesearchbasedonthesameexample showninFig.4.2. 4.3.1.2ProbabilisticClockMatching(PCM) Inthecrowded2.4GHzband,Bluetoothdevicesrarelyhopinthebasicmodebecause oftheimpactsofinterferencefromcoexistingwirelessdevices[17][28][54][20].To adaptspectrumuse,Bluetooththebasicchannelbyremappingbadsubchan- nelssubjectedtointerferencewithpseudo-randomlyselectedgoodsubchannels.Since theadaptedchannelmaydifferfromthebasicchannelinvariousphases,thehopping patternobservedbythescoutmaymismatchthebasichoppingsequenceevenatthe correctclock.Fig.4.3illustratestheimpactofsubchannelremappingusingthesameex- ampleshowninFig.4.2.Asillustratedinthee,bruteforcesearchmayfailtoa perfectmatchduetothepackettransmittedontheremappedsubchannel. Toacquirethepiconetclock c inthepresenceofinterference,BlueEarleveragesthe 28 followingkeyobservation.Whencomparinganobservedhoppingpattern P withthe basichoppingsequence atthecorrectclock,theratioofmismatchesshouldequalthe ratioofremappedsubchannels.AsrequiredbyFCC,BluetoothClassicmustuseatleast 20subchannelsforfrequencyhopping[47].Therefore,theratioofremappedsubchannels isatmost 59 79 .Hence,iftheratioofmismatchesataclock c islargerthan 59 79 , then c islikelyanincorrectclock. Drivenbytheaboveobservation,BlueEaremploysaprobabilisticclockmatching (PCM)algorithmforclockacquisition.Insteadofseekingaperfectlymatchedclock, BlueEardeterminesthecorrectclockbyeliminatingincorrectclocksbasedonthenumber ofmismatches.Aclockisasincorrectifthe95%intervalofitsmis- matchratioexceeds 59 79 .,let bethebasichoppingsequence, P = f p 0 ,.., p n g beasetofobservedpackets,and C = f c 0 , c 1 ,.. c j g and D = f d 0 , d 1 ,.. d j g bethesetsofclock candidatesandthecorrespondingmismatchesnumbers,respectively.Whencomparing P with ,thePCMalgorithmreturns C and D ,where d i isthenumberofmismatchesat clockcandidate c i .If c i isthecorrectclock,theratioofmismatches = d i n , n = j P j ,should beclosetotheratioofunusedsubchannels.Basedonthecentrallimittheory,thedistri- butionof p n ( d i n - ) shouldapproachnormalitywhen n isreasonablylarge.The95% intervalof canbeestimatedas d i n 2 ˙ p n ,where ˙ 2 isthevariance.Therefore, clock c i isdeterminedasincorrectif d i n - 2 ˙ p n 59 79 .Whenanewpacketiscaptured,the algorithmupdatesthemismatchratiosforremainingclockcandidates. 4.3.1.3AcceleratingClockAcquisition ThePCMalgorithmacquiresthecorrectclockbygraduallyeliminatingincorrectcandi- dates;thismayincursometimedelaywhilewaitingfornewpacketstobecaptured.To 29 reduceclockacquisitiondelay,BlueEarresortstoestimatethepiconetclock.Thatis,given asetofobservedpackets P ,theMLalgorithmderivesseveralsubsets P 1 ,.., P z ˆ P ,andin- vokesthePCMalgorithmtoobtaincorrespondingsetsofclockcandidates C 1 ,.., C z .From thelatersets,thealgorithmprobabilitydistributionofcandidatesanda candidatethatmaximizesthedistributionfunction.Inparticular,thealgorithmproceeds withthefollowingsteps. Step1: Input : P = f p 0 ,.., p n g and C = f c 0 ,.., c j g ,and b