INSTALL_PARSE_FAILED_NO_CERTIFICATES error in debug build Android Studio

Question

I just included the GCM library in my project and run the debug build. It fails with the above error. In my build.gradle file, I already have the signing configurations as below

 signingConfigs {
    signing_config {
        storePassword "123456"
        keyAlias "debug"
        keyPassword "debug"
        storeFile file("${rootDir}/app.keystore")
    }
}

My build gradle looks like this.

apply plugin: 'android-sdk-manager'
apply plugin: 'com.android.application'
apply plugin: 'com.google.gms.google-services'

signingConfigs {
    signing_config {
        storePassword "123456"
        keyAlias "debug"
        keyPassword "debug"
        storeFile file("${rootDir}/app.keystore")
    }
}


defaultConfig {
    applicationId "com.application.example"
    minSdkVersion 19
    targetSdkVersion 23
    versionCode project.versionCode
    versionName project.versionName
    multiDexEnabled true
}

buildTypes {
    debug {
        signingConfig android.signingConfigs.signing_config
        applicationIdSuffix ".debug"
       bla bla bla -- all server config related stuff
    }

    release {
        signingConfig android.signingConfigs.signing_config
        applicationIdSuffix 
       bla bla bla -- all server config related stuff
    }
}

compileOptions {
    sourceCompatibility 1.8
    targetCompatibility 1.8
}

dependencies {
//many dependencies
}

I use the same config to sign for release builds which work perfectly fine. Only on debug I get this error. Any help appreciated. Thanks!